网站开发需要那些技术人员,网页转向网站,建筑工程资质合作,免费wordpress主题破解描述 农夫约翰上个星期刚刚建好了他的新牛棚#xff0c;他使用了最新的挤奶技术。不幸的是#xff0c;由于工程问题#xff0c;每个牛栏都不一样。第一个星期#xff0c;农夫约翰随便地让奶牛们进入牛栏#xff0c;但是问题很快地显露出来#xff1a;每头奶牛都只愿意在她…描述 农夫约翰上个星期刚刚建好了他的新牛棚他使用了最新的挤奶技术。不幸的是由于工程问题每个牛栏都不一样。第一个星期农夫约翰随便地让奶牛们进入牛栏但是问题很快地显露出来每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期农夫约翰刚刚收集到了奶牛们的爱好的信息每头奶牛喜欢在哪些牛栏产奶。一个牛栏只能容纳一头奶牛当然一头奶牛只能在一个牛栏中产奶。 给出奶牛们的爱好的信息计算最大分配方案。 格式 PROGRAM NAME: stall4 INPUT FORMAT: (file stall4.in) 第一行 两个整数N (0 N 200) 和 M (0 M 200) 。N 是农夫约翰的奶牛数量M 是新牛棚的牛栏数量。 第二行到第N1行 一共 N 行每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 Si M)。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中在同一行一个牛栏不会被列出两次。 OUTPUT FORMAT: (file stall4.out) 只有一行。输出一个整数表示最多能分配到的牛栏的数量. SAMPLE INPUT 5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2SAMPLE OUTPUT 4 ^_^:本文参阅http://comzyh.tk/blog/archives/148/ COMZYH的博客不错的博客哦推荐 ^_^:解决最大二分匹配问题可以用网络流的最大流实现不过最大流比较复杂使用匈牙利算法编程较简单 ^_^:匈牙利算法核心思路 置边集M为空初始化谁和谁都没连着选择一个新的原点寻找增广路重复(2)操作直到找不出增广路径为止23步骤构成一个循环^_^:匈牙利算法过程演示 初始化清空从A所连接的点中找到一个未在本次循环中搜索过的点2并将2标记为搜索过因为2没有被连接过匹配A2结束上次开始新的循环将所有点标记为未搜索过搜索B找到一个未在本次循环中搜索过的点2标记为搜索过发现2被匹配过从2的父亲A寻找增广路递归搜索A{从A所连接的点中找到一个未在本次循环中搜索过的点51已经标记为绿色将5标记为搜索过因为5没有被匹配过匹配A5}找到增广路此处为增广路的关键结束上次开始新的循环将所有点标记为未搜索过搜索C找到一个未在本次循环中搜索过的点1并将1标记为搜索过,发现1未被匹配过匹配C1结束上次开始新的循环将所有点标记为未搜索过搜索D找到一个未在本次循环中搜索过的点1并将1标记为搜索过发现1被匹配过递归搜索1的源C寻找增广路{搜索C找到一个未在本次循环中搜索过的点5标记为搜索过发现5被匹配进一步返现没有其他可连接点返回找不到增广路}返回第9步搜索D找到一个未在本次循环中搜索过的点2发现2被匹配递归搜索2的源B寻找增广路{搜索B找到一个未在本次循环中搜索过的点3并将3标记为搜索过发现3未被匹配匹配B3返回找到}既然B另寻新欢匹配D2结束上次开始新的循环将所有点标记为未搜索过递归搜索D寻找增广路搜索E找到一个未在本次循环中搜索过的点2并将2标记为搜索过发现2被匹配过递归搜索2的源D寻找增广路{搜索D发现15均被匹配过返回找不到增广路}E无其他可连接节点放弃EE后无后续节点已经遍历A-E结束算法 1 #include iostream2 #include stdlib.h3 #include memory.h4 using namespace std;5 int tab[201][201];//邻接矩阵,不是真正意义的邻接矩阵,第一维对应牛,第二维对应牛棚6 int state[201],result[201];//stata:是否被搜索过;result:某牛栏对应的牛7 int n,m;8 int ans;//找到多少匹配9
10 int find(int x){// 匈牙利算法
11 for(int i1;im;i){
12 if(tab[x][i]1 !state[i]){
13 state[i]1;//标记为搜索过
14 if(result[i]0 || find(result[i])){//未被匹配过能找到一条增广路
15 result[i]x;//匹配i,x
16 return 1;//能找到新的匹配
17 }
18 }
19 }
20 return 0;
21 }
22 int main(){
23 int n1,t;
24 cinnm;
25 memset(tab,0,sizeof(tab));
26 for(int i1;in;i){
27 cinn1;
28 for(int j1;jn1;j){
29 cint;
30 tab[i][t]1;
31 }
32 }
33 for(int i1;in;i){
34 memset(state,0,sizeof(state));//清空是否搜索过数组
35 if(find(i)) ans;//找到新的匹配
36 }//完成后Result[i]保存着第i个牛栏对应的奶牛本题不用输出其他题有可能用
37 coutansendl;
38 return 0;
39 } 转载于:https://www.cnblogs.com/zjutlitao/p/3528203.html
