Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom5月前

04/5
15:37
二分图匹配 网络流

[bzoj 4808] 马

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

众所周知,马后炮是中国象棋中很厉害的一招必杀技。"马走日字"。本来,如果在要去的方向有别的棋子挡住(俗称"蹩马腿"),则不允许走过去。为了简化问题,我们不考虑这一点。马跟马显然不能在一起打起来,于是rly在一天再次借来了许多许多的马在棋盘上摆了起来……但这次,他实在没兴趣算方案数了,所以他只想知道在N×M的矩形方格中摆马使其互不吃到的情况下的最多个数。但是,有一个很不幸的消息,rly由于玩得太Happy,质量本来就不好的棋盘被rly弄坏了,不过幸好只是破了其中的一些格子(即不能再放子了),问题还是可以继续解决的。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

一行,两个正整数N和M。
接下来N行,每行M个数,要么为0,表示没坏,要么为1,表示坏了。
N<=200,M<=200

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一行,输出最多的个数。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2 3
0 1 0
0 1 0

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

求一个二分图的最大独立集。 最大独立集 = n - 最大匹配

两个互相影响的点之间连一条边,表示这两个点不可以同时取,然后跑网络流

 

[bzoj 4808] 马