Cow Contest Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 10967 Accepted: 6105
Description
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.
Input
* Line 1: Two space-separated integers: N and M * Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
Output
* Line 1: A single integer representing the number of cows whose ranks can be determined
Sample Input
5 5 4 3 4 2 3 2 1 2 2 5Sample Output
2题意：有n个地点，现在给出m条单向道路，问最少放多少人可以覆盖所有点，一个地点可以重复经过。
首先说一下传递闭包的知识：（转自：点击打开链接）
1、问题引入
一个有n个顶点的有向图的传递闭包为：有向图中的初始路径可达情况可以参见其邻接矩阵A，邻接矩阵中A[i,j]表示i到j是否直接可达，若直接可达，则A[i,j]记为1，否则记为0；两个有向图中i到j有路径表示从i点开始经过其他点（或者不经过其他点）能够到达j点，如果i到j有路径，则将T[i,j]设置为1，否则设置为0；有向图的传递闭包表示从邻接矩阵A出发，求的所有节点间的路径可达情况，该矩阵就为所要求的传递闭包矩阵。。。
例如：
有向图为：
由该有向图可以得到初始的邻接矩阵为：
那么warshall传递闭包算法的目的就是由邻接矩阵出发，进行探索求出最终的传递闭包：
通俗点：
所谓传递性，可以这样理解：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否相连。
思路：这题和POJ1422（点击打开）很像，但有个关键的差别，1422每个点只能经过一次，而这题可以重复经过。
如果只能经过一次，那么直接匈牙利就行，但如果可以经过多次，就需要先利用floyd求解下传递闭包加一些
新边再来求解， 具体求解方法就是枚举每个中间点， 枚举起点，终点， 题目保证无环的（如果有环，就不能匈牙利求最小路径覆盖了），所以大胆做就好了。
关于题目的进一步解释：转自：点击打开链接
比如直接求最短路径覆盖的话,上图情况如果求出1-2匹配，2-4匹配，那么3-2-5这条路径就已经被切断不存在了，因为2不能再走了
实际上2还是可以走的。按照上图，答案是5-最大匹配=5-2=3，实际上答案是2
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> using namespace std; const int maxn = 505; int link[maxn][maxn], match[maxn], book[maxn], n, m; vector<int> v[maxn]; void floyd() { for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) if(link[i][k]) for(int j = 1; j <= n; j++) if(link[k][j]) link[i][j] = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(link[i][j]) v[i].push_back(j); } int Find(int x) { for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(book[to]) continue; book[to] = 1; if(!match[to] || Find(match[to])) { match[to] = x; return 1; } } return 0; } int main() { while(~scanf("%d%d", &n, &m), n+m) { memset(link, 0, sizeof(link)); memset(match, 0, sizeof(match)); for(int i = 0; i <= n; i++) v[i].clear(); int x, y, ans = 0; for(int i = 1; i <= m; i++) scanf("%d%d", &x, &y), link[x][y] = 1; floyd(); for(int i = 1; i <= n; i++) { memset(book, 0, sizeof(book)); ans += Find(i); } printf("%d\n", n-ans); } return 0; }