标签存档：图论

【题目大意】有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

【题目大意】给定一个无向图，让你求从其中一个点出发，经过所有边，回到这个点（边可以重复走）的最短总长度。

【算法分析】

如果是直接给欧拉图的话，就是输出边权和就可以了。

否则的话，就先floyed，然后求出任意两点的最短路。

然后给每对度为奇数的点连边，然后就是求一般无向图的最小权匹配了。

这个有经典算法的，叫带花树，不过我不会

所以，只能用状态压缩动态规划水过。

【其它】暴力47MS。。。

【程序】

#include