首页 > 代码库 > 二分图
二分图
1. 啥是二分图？
严格点，就是把给出的N种可能配对关系拆成两边，假设是左、右俩边的话，如果一点无论怎么分，既得在左边，又得在右边，那么这就不是二分图了。 我们常见的题目通常是给出俩类不同的东西配对，比如男女配对（男1~N，女1~N），这样绝对不会出现男男配对这种情况，所以不需要检查是否构成二分图。 但如果就一类人编号为1~N，那么就得检查了。如HDU 2444, 需要检查二分图。
同时，在网络流中经常通过拆点拆出一种类似 ”二分图“ ，这种图中的一个点可能既在左边，又在右边，叫它二分图不太严谨，姑且称为”二部集“吧。
检查二分图的方法很简单，BFS 0/1染色法（当前点颜色为0，那么从这个点到达的点颜色就是1，如果到达点检测到已经染色，且颜色也是0，这个点明显就是既在左边，又在右边了) 。推荐使用邻接表（配合vector）。
代码如下。
vector<int> G[205];int color[205];bool judge(){ memset(color,-1,sizeof(color)); queue<int> Q; color[1]=0; Q.push(1); int next_color; while(!Q.empty()) { int x=Q.front();Q.pop(); next_color=!color[x]; for(int i=0;i<G[x].size();i++) { if(color[G[x][i]]==-1) { color[G[x][i]]=next_color; Q.push(G[x][i]); } else if(color[G[x][i]]==color[x]) return true; } } return false;}
@训练题：HDU 1829，给出虫子的关系，由此确定性别，不能出现同性恋。即二分图判断，一个虫子不能既在male又在female。
2. 二分图最大匹配
确定是二分图模型之后，你做的第一件事就是根据给出的配对关系确定最大能完成的匹配数。如HDU 2063，HDU 2444。
代码如下（使用邻接表）
bool dfs(int u){ for(int v=0;v<G[u].size();v++) { if(vis[G[u][v]]) continue; vis[G[u][v].p]=true; if(!link[G[u][v]]||dfs(link[G[u][v]])) { link[G[u][v]]=u; return true; } } } return false;}int main(){ int res=0; for(int i=1; i<=n; i++) { memset(vis,false,sizeof(vis)); if(dfs(i)) res++; }}
第二件事，就是最小点覆盖，即给出的每条关系中，俩个端点至少有一个被覆盖。最小点覆盖的建模通常由二维矩阵转化而来，如POJ 3041,HDU 1150，在二维矩阵中，只要x，y任一一个被覆盖，则所在行/列即被覆盖，而行/列中的点亦被全部覆盖。这样，当二分图达到最大匹配数时，二维矩阵中即 用了最少的行列覆盖所有点（原理很简单，每次匹配成功后，对应行列就当是永久消除了，下次就不用重复再对这些消除的行列操作了）。关键词：最小点覆盖数=最大匹配数。
第三件事，最小路径覆盖。
路径覆盖有两种，常规的是跳跃式路径，即给出的路径起始点不构成连续区间，如(1,3)是指P1和P3形成的路径，而不是P1-P2-P3形成的路径，由匈牙利算法的特性（想一想，为什么），可以求出最小的覆盖难度（最少覆盖的花费，注意不是最少的路径数）。关键词：最小路径覆盖数=顶点数-最大匹配数。
题目：
POJ1548（这题本来是LIS，但是可以转换成最小路径覆盖，天然的有向图建图，两两可到达的垃圾连条边，最后形成多个以一个点为中心的扩散图，这个中心即是起点，这个扩散图就是一个匹配，一条机器人路径，最小覆盖数就是覆盖所有点的最小难度，即至少派出的机器人数。）
POJ3020（采用无向图建图可以省去HASH重复路径，因为匈牙利不可以处理无向图，所以这题需要拆点，注意一旦拆点，u就不能放在X，v就不能放在Y了，u，v点要合并到一个集合里，详情见第一部分关于二分图和二部集的区别。本点放在X集，影子点放在Y集，如果有边（u，v），则u连v‘(本点连影子点），对邻接矩阵每个城市相邻四个点扫一下加下边，这样自动就连成的无向图。又是求最小覆盖难度。关键词：（无向图）最小路径覆盖数=顶点数-最大匹配数/2。
最小路径覆盖的第二种，就是坑爹的连续区间路径覆盖，这会真的求的是最少的路径数了。这类题目能够用匈牙利求解纯属偶然，网上很多人对于这类题目就看别人题解跟风一下（嗯，这题明显是最小路径覆盖） 然后就无脑贴代码，没有真正理解为什么最小路径覆盖的答案就是正确的。连续区间覆盖分为区间不可交叉和可交叉两种。
（不可交叉问题）最典型的是HDU 1151，伞兵覆盖问题。图中给出的路径是连续区间，而且不可交叉，一个伞兵可以走完区间所有点。看看这题的样例，第一组派出的是两个伞兵，完成的是两个匹配，（1,3）（3,4），匈牙利可没有处理连续区间覆盖的能力，其实并没有覆盖所有点，但是顶点数-最大匹配数确实是正确的答案，原因就是一个偶然，那就是此时最小覆盖难度=最少派出的伞兵数（原因：跳跃式覆盖中的独立点需要另开1个单位的花费，但是区间覆盖不会有独立点的花费，独立点的花费必然花在一条路径当中，而且数据保证所有点一定能覆盖）。第二组样例更明显。这类问题切记不要理解成：匈牙利在做一个连续区间的匹配，其实只是在做两个点的匹配而已。能覆盖连续区间只是问题转化的偶然。
（可交叉问题） POJ2594, 匈牙利造成的偶然并不能处理区间交叉覆盖，所以对于此类问题，先用floyd做一边传递闭包，把路径合并一下，然后在使用匈牙利。
第四件事, 最大独立集。
其实就是匹配的相反情况。匹配求的是最大多少点扯入一个关系，最大独立集求的就是最多的点没有扯入关系。最大独立集数=顶点数-最大匹配数。
3. 二分图的完美匹配和费用流问题。
所谓的完美匹配，其实属于加权匹配问题。所以诞生出最大权，最小权两种求法。注意，加权匹配中有两个要素：匹配数，权和。匹配数最优先，权和次优先，这点在处理最小权的时候比较清楚，保证权最小是在匹配数尽可能大的前提下的。所以KM找增广路的基础还是匈牙利，只不过加了权的择优选择部分。
之所以叫完美匹配，也叫100%匹配，是因为通常给出的匹配条件能够让所有元素的匹配，在这个100%匹配条件下找最优权，而不会出现某个元素漏配的情况。当然，有时候给出的图确实有些点是孤立的，没法匹配，这时候再叫它完美匹配不太合适，姑且就称为加权匹配吧。
说到加权匹配，就不得不扯费用流。几乎所有单向加权匹配问题都可以用费用流建模解决。建模的方案如下： 超级源点连所有X元素，费用0，流量1。X-Y有边则连，费用为权，流量随意（1或inf皆可）。所有Y连超级汇点，费用0，流量1。原理不难理解，毕竟二分图也是图，网络流也适用。不过，如果是双向加权匹配，渣渣还没想到怎么建模，T^T。
KM算法值得在意的是O（n^3)的slack优化，虽然很多人都说不明显，不过还是加上去吧。
这里贴下最小权的代码，HDU1853。
#include "iostream"#include "cstdio"#include "cstring"using namespace std;int n,m;int link[301],LX[301],RX[301],W[301][301],slack[301];bool S[301],T[301];const int inf=100000000;bool dfs(int u){ S[u]=true; for(int v=1;v<=n;v++) { if(T[v]) continue; int t=LX[u]+RX[v]-W[u][v]; if(!t) { T[v]=true; if(!link[v]||dfs(link[v])) { link[v]=u; return true; } } else if(t<slack[v]) slack[v]=t; } return false;}void update(){ int a=1<<30; for(int i=1;i<=n;i++) //ny if(!T[i]&&slack[i]<a) a=slack[i]; for(int i=1;i<=n;i++) //nx if(S[i]) LX[i]-=a; for(int i=1;i<=n;i++) //ny if(T[i]) RX[i]+=a; else slack[i]-=a;}int KM(){ memset(link,0,sizeof(link)); memset(RX,0,sizeof(RX)); for(int i=1;i<=n;i++) //nx for(int j=1;j<=n;j++) //ny LX[i]=max(LX[i],W[i][j]); for(int i=1;i<=n;i++) //nx { for(int j=1;j<=n;j++) slack[j]=inf; while(1) { memset(S,0,sizeof(S)); memset(T,0,sizeof(T)); if(dfs(i)) break; else update(); } } int res=0; for(int i=1;i<=n;i++) //ny { if(link[i]) res+=W[link[i]][i]; if(!link[i]||W[link[i]][i]==-inf) return 1; //未匹配情况 } return res;}int main(){ int U,V,C; while(scanf("%d%d",&n,&m)!=-1) { for(int i=1;i<=n;i++) //最小权初始化 for(int j=1;j<=n;j++) W[i][j]=-inf; for(int i=1;i<=m;i++) { scanf("%d%d%d",&U,&V,&C); W[U][V]=-C; //最大权则正 } int ans=-KM(); printf("%d\n",ans); memset(slack,0,sizeof(slack)); memset(LX,0,sizeof(LX)); } return 0;}
@加权匹配与建模。
HDU 2255 赤裸裸的最大权匹配，人配房子即可。
HDU 1853 环图问题，意思是说在一个有向图中绕多个圈把所有点走完，问最少花费。这题的建模真的很坑，之所以用匹配来解决，是因为把所有点放到X中，对于一个环计算费用，只需要link取出其邻接边即可取出费用了。如1-2-3-1，4-5-6-4这个两个环图，只要for（1..6) 挨个扫下W[link[i]][i]即可，根本不需要考虑环结构（其实就是最后首尾连接问题，费用流建模处理这个问题就十分棘手）。
XCOJ 1047 山东OI 06年的省选题，早期ACM/OI界对于二分图重视不够，你会发现上交ACM早期模板没有二分图这部分内容，导致这题是省选难度。赤裸裸的最小权匹配，不过费用计算比较麻烦一点，W[i][j]记得不要算上已经在目标仓库的量，W=总量-目标仓库的量。
UVALive 4043 , 07年区域赛欧洲赛区的一个神题，坐标系里黑白配，且任意匹配不能相交。按照大白书上说法是利用三角形两边之和大于第三边的几何性质。（假设a1-b1，a2-b2相交），则d（a1+b1）+d（a2+b2）>d(a1+b2)+d(a2+b1)，进行最小权匹配，费用为两点距离，这样就能保证绝对不相交。orz，我的智商实在不足以做区域赛的题。但是这题还有坑的地方，就是这次的权是浮点数，找增广路时条件要改。 double t=LX[u]+RX[v]-W[u][v]; if(fabs(t)<eps) {进行增广},eps=1e-10,即最小浮点数。这样做的原因就是计算的时候double约去某些小数位，产生误差。所以条件不是t=0，而是t<eps就增广。
HDU 5045，2014上海网赛被秒的二分图。防止相差超过1小时的方法就是，先按每个人一题分配。比如有3个人5题，第一轮先把前3题分给3个人，然后第二轮再把后3（补0）分给三个人。这样做（m/n）+1次KM就行了。要注意一开始概率数组要清0，防止最后补的一轮越界导致KM结果异常。
HDU 5045，2014上海网赛被秒的二分图。防止相差超过1小时的方法就是，先按每个人一题分配。比如有3个人5题，第一轮先把前3题分给3个人，然后第二轮再把后3（补0）分给三个人。这样做（m/n）+1次KM就行了。要注意一开始概率数组要清0，防止最后补的一轮越界导致KM结果异常。
二分图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。