月老的难题
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描写叙述
月老准备给n个女孩与n个男孩牵红线。成就一对对美好的姻缘。
如今，因为一些原因，部分男孩与女孩可能结成幸福的一家，部分可能不会结成幸福的家庭。
如今已知哪些男孩与哪些女孩假设结婚的话。能够结成幸福的家庭。月老准备促成尽可能多的幸福家庭，请你帮他找出最多可能促成的幸福家庭数量吧。
如果男孩们分别编号为1~n,女孩们也分别编号为1~n。
- 输入
- 第一行是一个整数T,表示測试数据的组数(1<=T<=400)
每组測试数据的第一行有两个整数n,K。当中男孩的人数与女孩的人数都是n。(n<=500,K<=10 000)
随后的K行。每行有两个整数i,j表示第i个男孩与第j个女孩有可能结成幸福的家庭。(1<=i,j<=n) - 输出
- 对每组測试数据。输出最多可能促成的幸福家庭数量
- 例子输入
1
3 4
1 1
1 3
2 2
3 2- 例子输出
2
- 来源
- 经典题目
- 上传者
题解：用邻接矩阵TLE，换成链式前向星才过。匈牙利模板题。
#include <stdio.h>
#include <string.h>
#define maxn 505
#define maxm 10010 int n, k, id;
int head[maxn], B[maxn];
bool vis[maxn];
struct Node {
int v, next;
} E[maxm]; void addEdge(int u, int v) {
E[id].v = v; E[id].next = head[u];
head[u] = id++;
} bool findPath(int x) {
int i, v;
for(i = head[x]; i != -1; i = E[i].next) {
v = E[i].v;
if(!vis[v]) {
vis[v] = true;
if(!B[v] || findPath(B[v])) {
B[v] = x; return true;
}
}
}
return false;
} int MaxMatch() {
int ans = 0;
for(int i = 1; i <= n; ++i) {
memset(vis, 0, sizeof(bool) * (n + 1));
if(findPath(i)) ++ans;
}
return ans;
} int main() {
// freopen("stdin.txt", "r", stdin);
int t, u, v;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &k);
memset(head, -1, sizeof(int) * (n + 1));
memset(B, 0, sizeof(int) * (n + 1));
id = 0;
while(k--) {
scanf("%d%d", &u, &v);
addEdge(u, v);
}
printf("%d\n", MaxMatch());
}
return 0;
}