首页 > 代码库 > 二分图匹配

二分图匹配

学了二分图,整个人都不好了,赶紧趁热打铁敲个日志巩固下记忆。
二分图,就是将一个图分为2个点集后,每个点集内部任意两点之间不存在边,即每一条边都连接在不同点集中的两个点。
匹配,是一个边集,且任两条边不相邻,即不存在公共点。
相关算法:
    ①最大匹配问题:
        顾名思义,就是找到给定图中边数最多的匹配。解决这一问题,可以采用网络流进行构图,或者利用匈牙利算法构造匈牙利树,这
    里讨论后一种做法。
        显然,空集也是一种匹配,那么我们可以从空集开始,对当前解一步步进行优化,使在满足匹配的前提下,边集尽可能大,或说进行
    增广。对于当前匹配,我们可以从一个未覆盖点开始,从这个点的连边进行搜索,直到找到另一个未覆盖点。因起点和终点都是未覆盖
    点,所以起始边和终边都是未匹配边,中继点一定是已覆盖点,然后易得知此路径上的边一定是已匹配边和未匹配边交错。要让边集仍
    满足匹配,且将起点和终点都被覆盖,只需要把路径上各边都取反,即舍去所有已匹配边,取用所有未匹配边,这时我们便可得到一个
    更优解。
        考虑对此算法进行优化,假如已某一点为起点无法找到增广路,那么在以后的查找中也不需要考虑该点的增广路,证明的话自己画个
    图大概就明白了。

技术分享匈牙利

 ②二分图最大点独立集:
    独立集:一个点集,满足其中所以点之间都没有边相邻。
    可以证明,二分图最大点独立集点数=总点数-最大匹配边数。证明如下:
        对于任意未被匹配的点,假如它们之间有连线,必定存在更优匹配,矛盾。对于已匹配点,由于减去的是边数,我们可以考虑只留下
    每条边的其中一个端点,这是可以保证独立。对于一个组未匹配点和已匹配点,如果他们之间存在连线,我们可以把这个已匹配点转为
    其匹配点,若该匹配点仍与未匹配点相连,易得到一个更优的匹配解,矛盾,得证。
    ③最优匹配问题:
        原最大匹配问题的变种,所有边都有一个权值,求边权和最大的匹配解。这时需要用到KM算法(全称是Kuhn-Munkras)。
        我们可以设二分图中两个点集中的每个点各有一个标记A[i]和B[i],在整个过程中保证对于边w(i,j)满足A[i]+B[i]≥w(i,j)。假如把所有
    A[i]+B[i]=w(i,j)的边组合为一个导出子图,假如这个子图存在完美匹配(即点完全覆盖),那么这个完美匹配一定是原图的最优匹配,但
    假如不存在完美匹配,我们需要改变点标记,使更多边进入子图,慢慢使子图存在完美匹配。我们可以设A[i]=maximine(w(i,j)) j∈V,
    B[i]=0。当我们找不到完美匹配时,便得到一棵交错树,可以取一个值lack,将A[i]减去lack,B[i]加上lack。此时,对于本已在树中的边或
    两顶点都不在树上时,A[i]+B[i]值不变,仍在树中或仍不在树中。对于有一个点在树上,其A[i]+B[i]值增大或减小,那么该边就有可能进
    入相等子图,于是子图得到扩大。这个lack就取能让新边进入的最小值就行。不断进行该操作,最后可得到一个完美匹配。

updata at 2017.4.13

  补了一波最大权匹配的KM算法,这里有个模版:

技术分享
#include<cstdio>#include<cstring>#include<algorithm>#define MN 1001#define ll long long#define INF 1e7using namespace std;int read_p,read_ca,read_f;inline int read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<0||read_ca>9) read_f=read_ca==-?-1:read_f,read_ca=getchar();    while(read_ca>=0&&read_ca<=9) read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}int m,n,nl,nr,dis[MN][MN],A[MN],B[MN],la,li[MN],sla[MN],t=0;ll mmh;bool va[MN],vb[MN];char s[MN];inline int abs(int x){return x<0?-x:x;}inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}bool find(int x){    va[x]=1;    for (int i=1;i<=n;i++)    if (!vb[i]){        if (A[x]+B[i]==dis[x][i]){            vb[i]=1;            if (li[i]==0||find(li[i])) return li[i]=x,1;        }else sla[i]=min(sla[i],A[x]+B[i]-dis[x][i]);    }    return 0;}void work(){    register int i,j;    for (i=1;i<=n;i++) li[i]=B[i]=0,A[i]=-INF;    for (i=1;i<=n;i++)    for (j=1;j<=n;j++) if (A[i]<dis[i][j]) A[i]=dis[i][j];    for (i=1;i<=n;i++){        if (A[i]==-INF){puts("-1");return;}        for (j=1;j<=n;j++) sla[j]=INF;        for (;;){            memset(va,0,sizeof(va));            memset(vb,0,sizeof(vb));            if (find(i)) break;            la=INF;            for (j=1;j<=n;j++) if (!vb[j]&&sla[j]<la) la=sla[j];            if (la==INF){puts("-1");return;}            for (j=1;j<=n;j++){                if (va[j]) A[j]-=la;                if (vb[j]) B[j]+=la;else sla[j]-=la;            }        }    }    mmh=0;    for (i=1;i<=n;i++) mmh+=A[i]+B[i];    printf("%lld\n",mmh);}int main(){    while (~scanf("%d%d%d",&nl,&nr,&m)){        t++;n=max(nl,nr);        for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++) dis[i][j]=(i<=nl&&j<=nr)?-INF:0;        while (m--){            int x=read()+1,y=read()+1,z=read();            if (z<0) continue;            if (dis[x][y]<z) dis[x][y]=z;        }        printf("Case %d: ",t);        work();    }}
KM dfs
技术分享
#include<queue>#include<cstdio>#include<cstring>#include<algorithm>#define MN 401#define ll long longusing namespace std;ll read_p,read_ca,read_f;inline ll read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<0||read_ca>9) read_f=read_ca==-?-1:read_f,read_ca=getchar();    while(read_ca>=0&&read_ca<=9) read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}queue<ll> q;ll n,nl,m,li[MN],x,y,num=0,to[MN],pre[MN];bool va[MN],vb[MN];ll A[MN],B[MN],sla[MN],z,dis[MN][MN],mmh=0;inline ll max(ll a,ll b){return a>b?a:b;}inline ll min(ll a,ll b){return a<b?a:b;}inline void Connect(ll x){    while (x) li[x]=pre[x],swap(to[pre[x]],x);}inline void bfs(ll x){    q.push(x);va[x]=1;    for(;;){        while (!q.empty()){            ll k=q.front();q.pop();            for (ll i=1;i<=n;i++)            if (!vb[i]){                ll t=A[k]+B[i]-dis[k][i];                if (t>sla[i]) continue;                pre[i]=k;                if (!t) if (vb[i]=1,!li[i]){Connect(i);return;}else va[li[i]]=1,q.push(li[i]);else sla[i]=t;            }        }        ll t=1e18;        for (ll i=1;i<=n;i++)        if (!vb[i]) t=min(t,sla[i]);        for (ll i=1;i<=n;i++){            if (va[i]) A[i]-=t;            if (vb[i]) B[i]+=t;else sla[i]-=t;        }        for (ll i=1;i<=n;i++)        if (!vb[i]&&!sla[i])        if (vb[i]=1,!li[i]){Connect(i);return;}else va[li[i]]=1,q.push(li[i]);    }}int main(){    register ll i,j;nl=read();    n=max(nl,read());m=read();    while (m--) x=read(),y=read(),z=read(),dis[x][y]=max(dis[x][y],z),A[x]=max(A[x],z);    for (i=1;i<=n;i++) memset(va,0,sizeof(va)),memset(vb,0,sizeof(vb)),memset(sla,63,sizeof(sla)),bfs(i);    for (i=1;i<=n;i++) mmh+=A[i]+B[i];    printf("%lld\n",mmh);    for (i=1;i<=nl;i++)    if (!dis[i][to[i]]) printf("0 ");else printf("%d ",to[i]);}
KM bfs

听说bfs会比dfs快,但是我的bfs还是在uoj上T掉了。

例题看这吧:http://972169909-qq-com.iteye.com/blog/1184514

二分图匹配