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算法
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define MAXN 510 5 using namespace std; 6 int n,m,k;///x,y集合中点的个数 7 int maps[MAXN][MAXN];///邻接矩阵 8 int cx[MAXN];///匹配关系,cx[1]=2表示男1和女2约会 9 int cy[MAXN]; 10 int vis[MAXN];///顶点访问状态数组，1访问过，0未访问过 11 int path(int x)///x为任何一个女生 12 { 13 int i; 14 for(i=1; i<=n; i++)///i为男生 15 { 16 if(maps[x][i]&&!vis[i]) 17 { 18 vis[i]=1; 19 if(!cx[i]||path(cx[i])) 20 { 21 cx[i]=x; 22 cy[x]=i; 23 return 1; 24 } 25 } 26 } 27 return 0; 28 } 29 int MaxMatch() 30 { 31 int res=0; 32 int i; 33 memset(cy,0,sizeof(cy)); 34 memset(cx,0,sizeof(cx));///初始化为0 35 for(i=1; i<=m; i++) 36 { 37 memset(vis,0,sizeof(vis)); 38 if(path(i)) 39 { 40 res++; 41 } 42 } 43 return res; 44 } 45 int main() 46 { 47 int i; 48 int a,b; 49 while(scanf("%d",&k)!=EOF) 50 { 51 if(k==0) 52 { 53 break; 54 } 55 scanf("%d%d",&m,&n); 56 memset(maps,0,sizeof(maps)); 57 for(i=0; i<k; i++) 58 { 59 scanf("%d%d",&a,&b); 60 maps[a][b]=1; 61 } 62 printf("%d ",MaxMatch()); 63 } 64 return 0; 65 }
BFS实现：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define MAXN 510 6 using namespace std; 7 int nx,ny;///x,y集合中点的个数 8 int maps[MAXN][MAXN];///邻接矩阵 9 int cx[MAXN],cy[MAXN];///cx[i]表示最终求得的最大匹配中与xi匹配的Y节点 10 int pre[MAXN];///x每一个点的上一个节点 11 int vis[MAXN];///标志一个点在找增广路的同时是否被访问过 12 int MaxMatch() 13 { 14 int i,j,y; 15 int res=0;///所求得的最大匹配数 16 memset(cx,0,sizeof(cx)); 17 memset(cy,0,sizeof(cy)); 18 memset(vis,0,sizeof(vis)); 19 for(i=1; i<=nx; i++) 20 { 21 if(!cx[i]) 22 { 23 queue<int>q; 24 q.push(i); 25 pre[i]=-1; 26 int flag=0;///标志是否找到了增广路 27 while(!q.empty()&&!flag) 28 { 29 int u=q.front(); 30 q.pop(); 31 for(int v=1; v<=ny&&!flag; v++) 32 { 33 if(maps[u][v]&&vis[v]!=i) 34 { 35 vis[v]=i; 36 q.push(cy[v]);///将于y匹配的x点放入队列 37 if(cy[v]!=0)///没有增广路 38 { 39 pre[cy[v]]=u;///记录x点的顺序 40 } 41 else///找到增广路 42 { 43 flag=1; 44 int d=u,e=v; 45 while(d!=-1)///将原来匹配的边去掉加入原来不在匹配中的边 46 { 47 int t=cx[d]; 48 cx[d]=e; 49 cy[e]=d; 50 d=pre[d]; 51 e=t; 52 } 53 } 54 } 55 } 56 } 57 if(cx[i]!=0)///新增一个匹配的边 58 { 59 res++; 60 } 61 } 62 } 63 return res; 64 } 65 int main() 66 { 67 int i; 68 int a,b; 69 int k; 70 while(scanf("%d",&k)!=EOF) 71 { 72 if(k==0) 73 { 74 break; 75 } 76 scanf("%d%d",&nx,&ny); 77 memset(maps,0,sizeof(maps)); 78 for(i=0; i<k; i++) 79 { 80 scanf("%d%d",&a,&b); 81 maps[a][b]=1; 82 } 83 printf("%d ",MaxMatch()); 84 } 85 return 0; 86 }