ACM 程序设计培训课件.ppt

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已饱和则结束，否