现在的位置: 首页 > 综合 > 正文

【贪心】【bzoj 3008】: 象棋

2017年04月21日 ⁄ 综合 ⁄ 共 246字 ⁄ 字号 评论关闭

http://www.lydsy.com/JudgeOnline/problem.php?id=3008


本题的难点是“移动过程中不能出现多颗棋子同时在某一格的情况”。

事实上,可以忽略此条件,因为棋子是相同的,

我们可以用合法的等效方案替代一棋子越过另一棋子的情况: A、B、C三格,A能在一步走到B,B也能在一步走到C。

在A的棋子需要走到存在棋子的B,接着走到C。此情形我们可以看成在B的棋子先走到C,接着在A的棋子走到B。


有了这个结论就可以套KM了,注意这题用费用流只有60分大哭

好久学学KM。。。

抱歉!评论已关闭.