Problem Description
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
Input
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
Output
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
Sample Input
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0
Sample Output
3
DFS算法
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 510
using namespace std;
int n,m,k;///x,y集合中点的个数
int maps[MAXN][MAXN];///邻接矩阵
int cx[MAXN];///匹配关系,cx[1]=2表示男1和女2约会
int cy[MAXN];
int vis[MAXN];///顶点访问状态数组，1访问过，0未访问过
int path(int x)///x为任何一个女生
{
int i;
for(i=; i<=n; i++)///i为男生
{
if(maps[x][i]&&!vis[i])
{
vis[i]=;
if(!cx[i]||path(cx[i]))
{
cx[i]=x;
cy[x]=i;
return ;
}
}
}
return ;
}
int MaxMatch()
{
int res=;
int i;
memset(cy,,sizeof(cy));
memset(cx,,sizeof(cx));///初始化为0
for(i=; i<=m; i++)
{
memset(vis,,sizeof(vis));
if(path(i))
{
res++;
}
}
return res;
}
int main()
{
int i;
int a,b;
while(scanf("%d",&k)!=EOF)
{
if(k==)
{
break;
}
scanf("%d%d",&m,&n);
memset(maps,,sizeof(maps));
for(i=; i<k; i++)
{
scanf("%d%d",&a,&b);
maps[a][b]=;
}
printf("%d\n",MaxMatch());
}
return ;
}
BFS实现：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 510
using namespace std;
int nx,ny;///x,y集合中点的个数
int maps[MAXN][MAXN];///邻接矩阵
int cx[MAXN],cy[MAXN];///cx[i]表示最终求得的最大匹配中与xi匹配的Y节点
int pre[MAXN];///x每一个点的上一个节点
int vis[MAXN];///标志一个点在找增广路的同时是否被访问过
int MaxMatch()
{
int i,j,y;
int res=;///所求得的最大匹配数
memset(cx,,sizeof(cx));
memset(cy,,sizeof(cy));
memset(vis,,sizeof(vis));
for(i=; i<=nx; i++)
{
if(!cx[i])
{
queue<int>q;
q.push(i);
pre[i]=-;
int flag=;///标志是否找到了增广路
while(!q.empty()&&!flag)
{
int u=q.front();
q.pop();
for(int v=; v<=ny&&!flag; v++)
{
if(maps[u][v]&&vis[v]!=i)
{
vis[v]=i;
q.push(cy[v]);///将于y匹配的x点放入队列
if(cy[v]!=)///没有增广路
{
pre[cy[v]]=u;///记录x点的顺序
}
else///找到增广路
{
flag=;
int d=u,e=v;
while(d!=-)///将原来匹配的边去掉加入原来不在匹配中的边
{
int t=cx[d];
cx[d]=e;
cy[e]=d;
d=pre[d];
e=t;
}
}
}
}
}
if(cx[i]!=)///新增一个匹配的边
{
res++;
}
}
}
return res;
}
int main()
{
int i;
int a,b;
int k;
while(scanf("%d",&k)!=EOF)
{
if(k==)
{
break;
}
scanf("%d%d",&nx,&ny);
memset(maps,,sizeof(maps));
for(i=; i<k; i++)
{
scanf("%d%d",&a,&b);
maps[a][b]=;
}
printf("%d\n",MaxMatch());
}
return ;
}