传送门
好题啊。
∑i<jpi,jK∗(200−K)>X\frac{\sum_{i<j}p_{i,j}}{K*(200-K)}>XK∗(200−K)∑i<jpi,j>X
=>∑i<jpi,j−XK(200−K)>0\sum_{i<j}p_{i,j}-XK(200-K)>0∑i<jpi,j−XK(200−K)>0
=>∑i<jpi,j+2XK∗K2−XK(199−K)>0\sum_{i<j}p_{i,j}+2X\frac {K*K}2-XK(199-K)>0∑i<jpi,j+2X2K∗K−XK(199−K)>0
=>∑i<j(pi,j+2X)−XK(199−K)>0\sum_{i<j}(p_{i,j}+2X)-XK(199-K)>0∑i<j(pi,j+2X)−XK(199−K)>0
然后拆边为点跑最大权闭合子图就行了。
话说double的dinic居然卡精度？
代码