【网络流24题】骑士共存问题(最大流)
题面
题解
这题本质上和没有任何区别
首先也是可以黑白染色
因为马必定会跳到异色点上面去
然后同样的,源点向一种颜色,另一种颜色向汇点连边
因为代价就是1,所以容量都是1
这里考虑的“相邻”的情况是马的跳法
因此,枚举从当前点能够到达的位置,连一条容量为INF的边过去
障碍直接特殊考虑就行了
最后的答案就是所有可以放的位置数减去最大流(最小割)
#include #include #include #include #include #include #include #include