3538. 田忌再赛马

这是中国历史上一个著名的故事，那是大约1919年前的事了

田忌将军是齐国的高官，他喜欢和国王、其他人一起赛马。田忌和国王都有三匹不同等级的马，分别是普通马、强化马和超级马。规则是一场比赛有三轮；每轮只能用一次某一匹马，单轮比赛的胜者从失败者手中拿走两百银元。

作为这个国家最有权势的人，国王最好的马，在每一个阶级他的马都比田忌的好，结果每次国王都从田忌那里拿走六百银元

田忌对此并不高兴，直到遇到中国历史上最著名的将领之一--孙膑。由于孙膑的一个小把戏，田忌在下一场比赛中赚回了两百银元。这是一个相当简单的把戏，用他的普通马对抗国王的超级马，这样他肯定会输掉那一轮，但后来他的强化马打败了国王的普通马，他的超级马打败了国王的强化马，多简单的把戏啊。

你觉得古代中国的高官田忌怎么样？如果田忌现在生活在这里，他一定会自嘲的。更重要的是，如果他现在参加ACM竞赛，他可能会发现赛马问题可以简单地看作是在二分图图中寻找最大匹配的问题。但是作为一个古代人，田忌不会编程，所以只能请你来帮忙。