BZOJ 1475 方格取数

发布于 2017-05-22  202 次阅读


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

题意:对于一个 n*n 的网格图,选择了一个点就不能选择与它相邻的点,求最大选择权值和...


最大点权独立集... 很显然,对于点 (i,j),记 i+j=g,与它相邻的点的 g 的奇偶性一定与 (i,j) 不同... 那么建图方式就是对于点 (i,j) 为奇,从 S 连一条边,若为偶,向 T 连一条边,权值皆为点权

而互斥的点之间,以权值为 inf 的点相连,确保不会被割下去。这样做后,一组流就对应一个选择方案了... 最小割即可.... 结果又因为智障错误调了 1h+.... 代码如下:

 


一个非常弱的准退役OIER