首页 > 代码库 > 二分图

二分图

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&lt;eps就增广。

HDU 5045,2014上海网赛被秒的二分图。防止相差超过1小时的方法就是,先按每个人一题分配。比如有3个人5题,第一轮先把前3题分给3个人,然后第二轮再把后3(补0)分给三个人。这样做(m/n)+1次KM就行了。要注意一开始概率数组要清0,防止最后补的一轮越界导致KM结果异常。

二分图