题面:棋盘覆盖
给定一个 NNN 行 NNN 列的棋盘,已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 222、宽度为 111 的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。
将棋盘黑白染色,从白格向黑格连边,使用匈牙利算法可过。但如果也从黑格向白格连边就会错误。然而蓝书中写的是无向边,所以请问本题为什么只需要连单项边,而类似的骑士放置不需要分黑白格。
无向边