关于二分图的建边
  • 板块学术版
  • 楼主渡鸦2007
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/9/1 21:31
  • 上次更新2023/10/27 12:51:34
查看原帖
关于二分图的建边
385748
渡鸦2007楼主2022/9/1 21:31

题面:棋盘覆盖

给定一个 NNNN 列的棋盘,已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 22、宽度为 11 的骨牌,骨牌的边界与格线重合(骨牌占用两个格子),并且任意两张骨牌都不重叠。

将棋盘黑白染色,从白格向黑格连边,使用匈牙利算法可过。但如果从黑格向白格连边就会错误。然而蓝书中写的是无向边,所以请问本题为什么只需要连单项边,而类似的骑士放置不需要分黑白格。

2022/9/1 21:31
加载中...