月老的难题
时间限制：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<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
#define MMINF(x) memset(x,INF,sizeof(x))
typedef long long LL;
const double PI=acos(-1.0);
const int N=20010;
struct info
{
int to;
int pre;
}E[N];
int head[N],cnt;
int match[N],vis[N];
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
memset(match,-1,sizeof(match));
}
void add(int s,int t)
{
E[cnt].to=t;
E[cnt].pre=head[s];
head[s]=cnt++;
}
int dfs(int u)
{
for (int i=head[u]; i!=-1; i=E[i].pre)
{
int v=E[i].to;
if(!vis[v])//没被访问过
{
vis[v]=1;//标记访问
if(match[v]==-1||dfs(match[v]))
//若没之前被匹配过或之后可以放到增广路里就合法
{
match[v]=u;//路径交换取反
match[u]=v;//路径交换取反
return 1;//成功找到增广路
}
}
}
return 0;
}
int main(void)
{
int tcase,i,a,b,n,k;
scanf("%d",&tcase);
while (tcase--)
{
init();
scanf("%d%d",&n,&k);
for (i=0; i<k; i++)
{
scanf("%d%d",&a,&b);
add(a,b+n);
}
int r=0;
for (i=1; i<=n; i++)
{
if(match[i]==-1)
{
MM(vis);
if(dfs(i))//这个点出发找到增广路
r++;
}
}
printf("%d
",r);
}
return 0;
}