lecture 09 2二分图及其应用.pptx

ACM 程序设计计算机学院 刘春英今天，请个假,下周调课(西安)每周一星（8）：/userstatus.php?user=0507212005072120第九讲二分图及其应用（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男1女2男2女3返回女1男1女2男2女3图示（2）：X0=男2V1={男2}V2 = ΦT(V1)={女1}Y=女1V1={男2，男1}V2 ={女1}Y=女2M←M⊕E(P)( 其中，P是从x0 →y的可增广道路 )返回匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：1．任给初始匹配M； 2．若X已饱和则结束，否则进行第3步； 3．在X中找到一个非饱和顶点x0， 作V1 ← {x0}, V2 ← Φ； 4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2； 5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M⊕E(P)，转2； 6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4； 女1男1男2女2X0=男2V1={男2}V2 = ΦT(V1)={女1}T(V1) != V2Y=女1V1