BZOJ 3175 [Tjoi2013] 攻击装置

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


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

题意:一个 n*n 的 01 网格图...0 可以放装置,装置的攻击范围是马的走法... 问最多放多少个装置....


匈牙利算法,由于之前的二分图最大匹配都是网络流水过... 所以今天学习一个... 结果狂 WA 狂 RE 了 1h....

对于一对可以互相攻击到且都能放置的点,连一条边,找二分图最大点独立集即可....

代码如下:

 


一个非常弱的准退役OIER