月老的难题
时间限制：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
典型的匈牙利算法模板，但是必须要用邻接表做，用邻接矩阵会超时#include<stdio.h> #include<string.h> #define MAX 10010 int head[MAX],cnt; int vis[MAX],girl[MAX]; int n,m; struct node { int u,v; int next; }edge[MAX]; void add(int u,int v) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } int find(int x) { int i,j; for(i=head[x];i!=-1;i=edge[i].next) { int y=edge[i].v; if(!vis[y]) { vis[y]=1; if(girl[y]==0||find(girl[y])) { girl[y]=x; return 1; } } } return 0; } int main() { int t,i,j; scanf("%d",&t); while(t--) { memset(head,-1,sizeof(head)); memset(girl,0,sizeof(girl)); cnt=0; scanf("%d%d",&n,&m); for(i=0;i<m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); } int sum=0; for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(find(i)) sum++; } printf("%d ",sum); } }