360免费建站app,网站开发培训排名,网站上传视频怎么做,html5可视化编辑器Problem DescriptionRPG girls今天和大家一起去游乐场玩#xff0c;终于可以坐上梦寐以求的过山车了。可是#xff0c;过山车的每一排只有两个座位#xff0c;而且还有条不成文的规矩#xff0c;就是每个女生必须找个个男生做partner和她同坐。但是#xff0c;每个女孩都有…Problem Description RPG girls今天和大家一起去游乐场玩终于可以坐上梦寐以求的过山车了。可是过山车的每一排只有两个座位而且还有条不成文的规矩就是每个女生必须找个个男生做partner和她同坐。但是每个女孩都有各自的想法举个例子把Rabbit只愿意和XHD或PQK做partnerGrass只愿意和linle或LL做partnerPrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题boss刘决定只让找到partner的人去坐过山车其他的人嘿嘿就站在下面看着吧。聪明的Acmer你可以帮忙算算最多有多少对组合可以坐上过山车吗 Input 输入数据的第一行是三个整数K , M , N分别表示可能的组合数目女生的人数男生的人数。0K10001N 和M500.接下来的K行每行有两个数分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。 Output 对于每组数据输出一个整数表示可以坐上过山车的最多组合数。 Sample Input 6 3 31 11 21 32 12 33 10 Sample Output 3 分析匈牙利算法。 code: View Code #includestdio.h#includestring.h#define clr(x)memset(x,0,sizeof(x))bool g[505][505];bool v[505];int l[505];int n,m;int find(int k){int i;for(i1;im;i) {if(g[k][i]!v[i]) { v[i]1; /* 男生 k 与女生 i 配对(i 未与别的男生配对); * 女生 i 与别的男生(l[i])配对了, * 但从与女生 i 配对的男生开始找, 可以找到另外一个可以匹配的 */if(l[i]0||find(l[i])) { l[i]k;return 1; } } }return 0;}int main(){int i,k,p,q,tot;while(scanf(%d,k),k) { scanf(%d%d,n,m); clr(g); clr(l);for(i0;ik;i) { scanf(%d%d,p,q); g[p][q]1; } tot0;for(i1;in;i) //每个男的找女友 { clr(v);if(find(i)) tot; } printf(%d\n,tot); }return 0;} 邻接表 View Code #includestdio.h#includestring.h#define N 1010struct node{int v;int next;}e[N*N];int k,m,n,h[N];int f[N];int s[N];int find(int x){int i,y;for(ih[x];i0;ie[i].next) { ye[i].v;if(!s[y]) { s[y]1;if(!f[y]||find(f[y])) { f[y]x;return 1; } } }return 0;}int main(){int i,j,k,r;while(scanf(%d,k),k) { scanf(%d%d,m,n);for(i1;im;i) h[i]-1;for(i1;in;i) f[i]0; rk0;while(k--) { scanf(%d%d,i,j); e[k].vj; e[k].nexth[i]; h[i]k; }for(i1;im;i) { memset(s,0,sizeof(s));if(find(i)) r; } printf(%d\n,r); }return 0;} 转载于:https://www.cnblogs.com/dream-wind/archive/2012/03/15/2397197.html
