(lecture092)二分图及其应用课件

ACM程序设计信息学院计算机应用系余腊生11/21/20221ACM程序设计信息学院计算机应用系11/20/20221今天，请个假,下周调课(西安)11/21/20222今天，请个假,11/20/20222每周一星（8）：0507212011/21/20223每周一星（8）：0507212011/20/20223第九讲二分图及其应用（BipartiteGraph&Applications）11/21/20224第九讲二分图及其应用11/20/20224主要内容什么是二分图二分图的最大匹配匈牙利算法二分图的最小顶点覆盖DAG图的最小路径覆盖二分图的最大独立集处理技巧11/21/20225主要内容什么是二分图11/20/20225什么是二分图？如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称该图为“二分图”（BipartiteGraph

）11/21/20226什么是二分图？如果一个图的顶点可以分为两个集合X和Y，图的所例：婚配问题男女11/21/20227例：婚配问题男女11/20/20227二分图的最大匹配

在二分图的应用中，最常见的就是最大匹配问题，很多其他的问题都可以通过转化为匹配问题来解决。11/21/20228二分图的最大匹配在二分图的应用中，最常见的就是最大匹如何求二分图的最大匹配呢？11/21/20229如何求二分图的最大匹配呢？11/20/20229经典算法：匈牙利算法11/21/202210经典算法：匈牙利算法11/20/202210/*hdoj_1150匈牙利算法月下版*/

#include<iostream>

#include<string>

#include<vector>

usingnamespacestd;

boolmark1[100],mark2[100];

intlist[100];

intn,m,edge,num;

vector<vector<int>>v;

booldfs(intto)

{

registerinti,point,s=list[to];

for(i=0;i<v[s].size();i++)

{

point=v[s][i];

if(!mark2[point])

continue;

mark2[point]=false;

if(list[point]==-1||dfs(point)){

list[point]=s;

returntrue;

}

}

returnfalse;

}

voidSolve()

{

inti,j,point;

boolflog=false;

memset(mark1,true,sizeof(mark1));

memset(list,-1,sizeof(list));

num=0;

for(i=0;i<n;i++)

{

for(j=0;j<v[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;i<n;i++)

{

if(mark1[i])

{

if(!v[i].empty()){

memset(mark2,true,sizeof(mark2));

for(j=0;j<v[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;

elsecout<<num<<endl;

}

intmain()

{

inti,j,s,d;

while(cin>>n)

{

if(n==0)break;

v.clear();

v.resize(n);

cin>>m>>edge;

for(i=0;i<edge;i++)

{

cin>>j>>s>>d;

v[s].push_back(d);

}

Solve();

}

return0;

}11/21/202211/*hdoj_1150匈牙利算法月下版*/

#incl匈牙利算法(求二分图最大匹配)谈匈牙利算法自然避不开Hall定理Hall定理：对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：|T(A)|>=|A|

11/21/202212匈牙利算法(求二分图最大匹配)谈匈牙利算法自然避不开Hall图示（1）：男1男2女1女2女3返回11/21/202213图示（1）：男1男2女1女2女3返回11/20/202213图示（2）：男1男2女1女2女3返回X0=男2V1={男2}V2=ΦT(V1)={女1}Y=女1V1={男2，男1}V2={女1}Y=女2M←M⊕E(P)(其中，P是从x0→y的可增广道路)11/21/202214图示（2）：男1男2女1女2女3返回X0=男211/20/2匈牙利算法是基于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；11/21/202215匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为图示（3）：男1男2女1女2返回X0=男2V1={男2}V2=ΦT(V1)={女1}T(V1)!=V2Y=女1V1={男2，男1}V2={女1}T(V1)=V211/21/202216图示（3）：男1男2女1女2返回X0=男211/20/202NOTE:

真正求二分图的最大匹配的题目很少，往往做一些简单的变化，比如——11/21/202217NOTE: 真正求二分图的最大匹配的题目很少，往往做一些简单变种1：

二分图的最小顶点覆盖 在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是 “二分图的最小顶点覆盖”。11/21/202218变种1：

二分图的最小顶点覆盖 在二分图中求最少的点，让每实例分析11/21/202219实例分析11/20/202219例：严禁早恋，违者开除！男生女生11/21/202220例：严禁早恋，违者开除！男生女生11/20/202220例：任务安排

有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai,如果它在机器B上运行，则机器A需要设置为模式bi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。——hdoj_1150（LRJ_p331）——ACM/ICPCBeijing200211/21/202221例：任务安排 有两台机器A和B以及N个需要运行的任务。每台机图示：结论：二分图的最小顶点覆盖数=二分图的最大匹配数a0a1a2a3a4b0b1b2b3b411/21/202222图示：结论：a0a1a2a3a4b0b1b2b3b411/2特别说明:此题需要注意的一点，具体参见：

/forum/read.php?tid=61&keyword=%B6%FE%B7%D611/21/202223特别说明:此题需要注意的一点，具体参见：11/20/2022变种2：

DAG图的最小路径覆盖 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。11/21/202224变种2：

DAG图的最小路径覆盖 用尽量少的不例：空袭（AirRaid）有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。——hdoj_1151

11/21/202225例：空袭（AirRaid）11/20/202225Sampleinput:

4

3

34

13

23Output:211/21/202226Sampleinput: 4

3

34

13

23O“空袭”示意图12344’3’2’1’132411/21/202227“空袭”示意图12344’3’2’1’132411/20/2结论：DAG图的最小路径覆盖数=节点数（n）-最大匹配数（m）关键：求二分图的最大匹配数11/21/202228结论：DAG图的最小路径覆盖数=11/20/202228变种3:

二分图的最大独立集GirlsandBoys

大学二年级的时候，一些同学开始研究男女同学之间的缘分。研究者试图找出没有缘分同学的最大集。程序的结果就是要输出这个集合中学生的数量。——hdoj_106811/21/202229变种3:

二分图的最大独立集GirlsandBoys输入数据格式：7

0:(3)456

1:(2)46

2:(0)

3:(0)

4:(2)01

5:(1)0

6:(2)01输出：5

11/21/202230输入数据格式：7

0:(3)456

1:(200’154326’5’4’3’2’1’6“GirlsandBoys”示意图11/21/20223100’154326’5’4’3’2’1’6“Girlsan结论：二分图的最大独立集数=节点数（n）—最大匹配数（m）关键：求二分图的最大匹配数11/21/202232结论：二分图的最大独立集数=11/20/202232AnyQuestions?11/21/202233AnyQuestions?11/20/202233附：二分匹配练习题：

(HDOJ)1068(二分图最大独立集=n-m)1150(二分图最小顶点覆盖= m)1151(二分图最小路径覆盖=n-m)11/21/202234附：二分匹配练习题：

(HDOJ)1068(二分图最大独别忘了，下周调课(西安)11/21/202235别忘了，下周调课(西安)11/20/202235课后一定要练习！11/21/202236课后一定要练习！11/20/202236ACM,天天见！

11/21/202237ACM,11/20/202237ACM程序设计信息学院计算机应用系余腊生11/21/202238ACM程序设计信息学院计算机应用系11/20/20221今天，请个假,下周调课(西安)11/21/202239今天，请个假,11/20/20222每周一星（8）：0507212011/21/202240每周一星（8）：0507212011/20/20223第九讲二分图及其应用（BipartiteGraph&Applications）11/21/202241第九讲二分图及其应用11/20/20224主要内容什么是二分图二分图的最大匹配匈牙利算法二分图的最小顶点覆盖DAG图的最小路径覆盖二分图的最大独立集处理技巧11/21/202242主要内容什么是二分图11/20/20225什么是二分图？如果一个图的顶点可以分为两个集合X和Y，图的所有边一定是有一个顶点属于集合X，另一个顶点属于集合Y，则称该图为“二分图”（BipartiteGraph

）11/21/202243什么是二分图？如果一个图的顶点可以分为两个集合X和Y，图的所例：婚配问题男女11/21/202244例：婚配问题男女11/20/20227二分图的最大匹配

在二分图的应用中，最常见的就是最大匹配问题，很多其他的问题都可以通过转化为匹配问题来解决。11/21/202245二分图的最大匹配在二分图的应用中，最常见的就是最大匹如何求二分图的最大匹配呢？11/21/202246如何求二分图的最大匹配呢？11/20/20229经典算法：匈牙利算法11/21/202247经典算法：匈牙利算法11/20/202210/*hdoj_1150匈牙利算法月下版*/

#include<iostream>

#include<string>

#include<vector>

usingnamespacestd;

boolmark1[100],mark2[100];

intlist[100];

intn,m,edge,num;

vector<vector<int>>v;

booldfs(intto)

{

registerinti,point,s=list[to];

for(i=0;i<v[s].size();i++)

{

point=v[s][i];

if(!mark2[point])

continue;

mark2[point]=false;

if(list[point]==-1||dfs(point)){

list[point]=s;

returntrue;

}

}

returnfalse;

}

voidSolve()

{

inti,j,point;

boolflog=false;

memset(mark1,true,sizeof(mark1));

memset(list,-1,sizeof(list));

num=0;

for(i=0;i<n;i++)

{

for(j=0;j<v[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;i<n;i++)

{

if(mark1[i])

{

if(!v[i].empty()){

memset(mark2,true,sizeof(mark2));

for(j=0;j<v[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;

elsecout<<num<<endl;

}

intmain()

{

inti,j,s,d;

while(cin>>n)

{

if(n==0)break;

v.clear();

v.resize(n);

cin>>m>>edge;

for(i=0;i<edge;i++)

{

cin>>j>>s>>d;

v[s].push_back(d);

}

Solve();

}

return0;

}11/21/202248/*hdoj_1150匈牙利算法月下版*/

#incl匈牙利算法(求二分图最大匹配)谈匈牙利算法自然避不开Hall定理Hall定理：对于二分图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有：|T(A)|>=|A|

11/21/202249匈牙利算法(求二分图最大匹配)谈匈牙利算法自然避不开Hall图示（1）：男1男2女1女2女3返回11/21/202250图示（1）：男1男2女1女2女3返回11/20/202213图示（2）：男1男2女1女2女3返回X0=男2V1={男2}V2=ΦT(V1)={女1}Y=女1V1={男2，男1}V2={女1}Y=女2M←M⊕E(P)(其中，P是从x0→y的可增广道路)11/21/202251图示（2）：男1男2女1女2女3返回X0=男211/20/2匈牙利算法是基于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；11/21/202252匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为图示（3）：男1男2女1女2返回X0=男2V1={男2}V2=ΦT(V1)={女1}T(V1)!=V2Y=女1V1={男2，男1}V2={女1}T(V1)=V211/21/202253图示（3）：男1男2女1女2返回X0=男211/20/202NOTE:

真正求二分图的最大匹配的题目很少，往往做一些简单的变化，比如——11/21/202254NOTE: 真正求二分图的最大匹配的题目很少，往往做一些简单变种1：

二分图的最小顶点覆盖 在二分图中求最少的点，让每条边都至少和其中的一个点关联，这就是 “二分图的最小顶点覆盖”。11/21/202255变种1：

二分图的最小顶点覆盖 在二分图中求最少的点，让每实例分析11/21/202256实例分析11/20/202219例：严禁早恋，违者开除！男生女生11/21/202257例：严禁早恋，违者开除！男生女生11/20/202220例：任务安排

有两台机器A和B以及N个需要运行的任务。每台机器有M种不同的模式，而每个任务都恰好在一台机器上运行。如果它在机器A上运行，则机器A需要设置为模式ai,如果它在机器B上运行，则机器A需要设置为模式bi。每台机器上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。请合理为每个任务安排一台机器并合理安排顺序，使得机器重启次数尽量少。——hdoj_1150（LRJ_p331）——ACM/ICPCBeijing200211/21/202258例：任务安排 有两台机器A和B以及N个需要运行的任务。每台机图示：结论：二分图的最小顶点覆盖数=二分图的最大匹配数a0a1a2a3a4b0b1b2b3b411/21/202259图示：结论：a0a1a2a3a4b0b1b2b3b411/2特别说明:此题需要注意的一点，具体参见：

/forum/read.php?tid=61&keyword=%B6%FE%B7%D611/21/202260特别说明:此题需要注意的一点，具体参见：11/20/2022变种2：

DAG图的最小路径覆盖 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。11/21/202261变种2：

DAG图的最小路径覆盖 用尽量少的不例：空袭（AirRaid）有一个城镇，它的所有街道都是单行的，并且每条街道都是和两个路口相连。同时已知街道不会形成回路。你的任务是编写程序求最小数量的伞兵，这些伞兵可以访问（visit）所有的路口。对于伞兵的起始降落点不做限制。——hdoj_1151

11/21/202262例：空袭（AirRaid）11/20/202225Sampleinput:

4

3

34

13

23Output:211/21/202263Sampleinpu