作者存档：edward_mj

【题目大意】给定一个无环有向图，然后求可以用重复点的最小路径覆盖。

【算法分析】既然可以用重复的，那么就可以用floyed求传递闭包，然后重复的相当于走过那条路了。然后求最小路径覆盖即可。

【HINT】记得最后要n-ans

【CODE】

#include

【题目大意】有N个女生，N个男生，给定一些边表示这两个人可以结婚。再给定一个初始匹配，表示这个男生和哪个女生结婚。初始匹配必定是合法的。然后让你求每个男生可以和哪几个女生结婚，使得所有人都能得到婚配。

【算法分析】如果男生A可以和女生B结婚，那么连边[A,B]，如果初始匹配[A,B],那么连边[B,A]，最后，如果在同一个强连通分量以内，则表示可以结婚。

其实就是二分图匹配中的寻找增广路的过程，可以自己体会。

【CODE】

#include

【题目大意】给定N只牛和M场比赛结果，问有多少牛的排名结果可以确定。（假设每只牛都有一个不同的力量值，大得肯定打赢小的）

【算法分析】如果A赢了B，那么连边[A,B],然后传递闭包。最后，如果某只牛的出度+入度=n-1的话，它的排名就已经确定了。

【其它】1A。这可能是除了A+Bproblem以外最短的程序了。。。水过留痕

【CODE】

#include

【题目大意】给定N个矩形和N个点，如果点在矩形内则连一条边，然后求哪些边是最大匹配的必须边。

【算法分析】就是用“试删法”，如果删了最大匹配数都没变，就不是必须边，否则就是。

【其它】1A

【code】

#include

【题目大意】给定一个N*M得矩阵，#表示不可以走，0..9表示走到这上面可以得到的分数（每个点只能采集一次）一开始你在左上角，只能向下走或向右走。然后有一些地方有传送门，可以选择无耗损地从这一点传到目标点，也可以选择不传，问最多能得到多少分。

【算法分析】先缩点，然后拓扑排序，最后用dp求最长路，输出就行了。

【其它】悲剧，RE了N遍，不过又MS并非RE得问题，我一开始把不能走到的点也算到DP序列里去了，居然一直RE。。。搞不懂为什么。改了以后终于AC。

【CODE】

#include