- 1、本文档共37页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Sample input: 433 41 32 3 Output: 2 精品文档 ACM 程序设计 计算机学院 刘春英 精品文档 今天, 请个假, 下周调课(西安) 精品文档 每周一星(8):精品文档 第九讲 二分图及其应用 (Bipartite Graph Applications) 精品文档 主要内容 什么是二分图 二分图的最大匹配 匈牙利算法 二分图的最小顶点覆盖 DAG图的最小路径覆盖 二分图的最大独立集 处理技巧 精品文档 什么是二分图? 如果一个图的顶点可以分为两个集合X和Y,图的所有边一定是有一个顶点属于集合X,另一个顶点属于集合Y,则称该图为“二分图”( Bipartite Graph ) 精品文档 例:婚配问题 男 女 精品文档 二分图的最大匹配 在二分图的应用中,最常见的就是最大匹配问题,很多其他的问题都可以通过转化为匹配问题来解决。 精品文档 如何求二分图的最大匹配呢? 精品文档 经典算法: 匈牙利算法 精品文档 /*hdoj_1150匈牙利算法 月下版 */#includeiostream#includestring#includevectorusing namespace std;bool mark1[100],mark2[100];int list[100];int n,m,edge,num;vectorvectorint v;bool dfs(int to){register int i,point,s = list[to];for(i=0;iv[s].size();i++){point = v[s][i];if(!mark2[point])continue;mark2[point] = false;if(list[point]==-1 || dfs(point)){list[point] = s;return true;}}return false;} void Solve(){int i,j,point;bool flog = false;memset(mark1,true,sizeof(mark1));memset(list,-1,sizeof(list));num=0;for(i=0;in;i++){for(j=0;jv[i].size();j++)if(list[v[i][j]] == -1){mark1[i] = false;list[v[i][j]] = i;num++;if(i==0) flog = true;break;} } for(i=0;in;i++){if(mark1[i]){if(!v[i].empty()){memset(mark2,true,sizeof(mark2));for(j=0;jv[i].size();j++){point = v[i][j];if(!mark2[point]) continue;mark2[point] = false;if(list[point] == -1 || dfs(point)){list[point] = i;num++;break;} } }mark1[i] = false; } } if(flog || list[0] != -1)cout num-1 endl;else cout num endl;} int main(){int i,j,s,d;while(cinn){if(n == 0)break;v.clear();v.resize(n);cin m edge;for(i=0;iedge;i++){cin j s d;v[s].push_back(d);} Solve();} return 0;} 精品文档 匈牙利算法(求二分图最大匹配) 谈匈牙利算法自然避不开Hall定理 Hall定理:对于二分图G,存在一个匹配M,使得X的所有顶点关于M饱和的充要条件是:对于X的任意一个子集A,和A邻接的点集为T(A),恒有: |T(A)| = |A| 精品文档 图示(1): 男1 男2 女1 女2 女3 返回 精品文档 图示(2): 男1 男2 女1 女2 女3 返回 X0=男2 V1={男2} V2 = Φ T(V1)={女1} Y=女1 V1={男2,男1} V2 ={女1} Y=女2 M←M⊕E(P) ( 其中,P是从x0 →y的可增广道路 ) 精品文档 匈牙利算法是基于Hall定理中充分性证明的思想,其基本步骤为: 1.任给初始匹配M; 2.若X已饱和则结束,否
文档评论(0)