BZOJ 2661 [BeiJing wc2012] 连连看

发布于 2017-06-23  149 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2661

题意:在 [a,b] 中若任意两数 x,y(设 x>y)的平方差 x2-y2 是一个完全平方数 z2,并且 y 与 z 互质,那么可以删除 x,y,获得 x+y 收益,求最大收益


拆点,暴力建图的想法是显然的... 也是正确的,对于每个点 i,拆为点\(x_i\) 和\(y_i\),若 i,j 两点可以消除,则连\(x_i,y_j\) 和\(x_j,y_i\),费用均为两数之和,我们称这两条边为一对边

显然在跑最大费用流的时候如果跑了一对边中的一条,那么另外一条一定也是可以跑的最优情况。最大费用最大流在增广时改为最长路即可

 


一个非常弱的准退役OIER