题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=239
解题思路:
二分图的最大匹配。模板题,开始学习二分图了。。。
匈牙利算法。
代码如下:
#include<cstdio> #include<cstring> using namespace std; #define N 10010 #define M 510 int head[M], next[N], key[N], num; int match[M]; bool use[M]; void add(int u, int v) //hash表存图 { key[num] = v; next[num] = head[u]; head[u] = num++; } bool find(int u) //匈牙利算法 { int temp; for(int i = head[u]; i != -1; i = next[i]) { temp = key[i]; if(!use[temp]) { use[temp] = true; if(match[temp] == -1 || find(match[temp])) //增广路 { match[temp] = u; return true; } } } return false; } int sum(int n) //最大匹配数 { int sumall = 0; for(int i = 1; i <= n; ++i) { memset(use, false, sizeof(use)); if(find(i)) sumall++; } return sumall; } int main() { int ncase; int allnum, relation; int u, v; scanf("%d", &ncase); while(ncase--) { num = 0; memset(head, -1, sizeof(head)); memset(match, -1, sizeof(match)); scanf("%d%d", &allnum, &relation); for(int i = 0; i < relation; ++i) { scanf("%d%d", &u, &v); add(u, v); } printf("%d\n", sum(allnum)); } return 0; }