題解 P3386 【【模闆】二分圖比對】

題目連結

首先呢聲明一下，本寶寶發這篇題解隻是為了（goto a;）

個人還是比較喜歡跑dinic暴力跑最大流。。。竟然比匈牙利還快。。

如果說不懂網絡流的~~蒟蒻~~大佬們。

可以看看

這個

（反正我就是在這篇文章看懂的）

好啦，言歸正傳。

a:本寶寶想解釋一下為什麼這道題可以用網絡流水過233....

首先我們看看二分圖的概念。标準概念是：

簡單的說，一個圖被分成了兩部分，相同的部分沒有邊，那這個圖就是二分圖，二分圖是特殊的圖。（摘自

這裡

）

如果你看不懂的話，那麼請看某大佬給寶寶講的時候的解釋：

~~一群漢子和一群妹子比對。沒有基友也沒百合，不能開後宮，這就是二分圖。最大比對就是求能組成的CP最多多少對~~  可能題解不過就是因為這句話233（逃~）

網絡流最重要的是要建圖！建圖！建圖！那麼看看這道題怎麼建圖。

我們發現對于左邊的n個點和右邊的m個點。如果說最好的情況下。比對的~~個~~對數是$min(m,n)$也就是說，我們左邊盡可能的通過已有的邊流到右半部分統計一下流到右半部分的容量最大值就是答案了（當然是要邊的容量都是1的時候最簡單了）。

是以我們将源點S設在左半部分左邊，向左邊所有的點連一條容量為1的邊。彙點T設在右半部分的右邊。從所有的右半部分的點連向彙點一條容量為1的邊，暴力跑一邊dicnic就好啦。

是以建邊代碼：

scanf("%d%d%d",&n1,&m1,&e1);
    n=n1+m1+2;//源點編号為1，彙點編号為總點數+1
    for(int i=1;i<=n1;i++)
    {
        add(1,i+1,1);//空過源點，是以i+1，這裡在連接配接源點和左部點。
        add(i+1,1,1);
    }
    for(int i=1;i<=e1;i++)
    {
        int u,v;//連已有的邊
        scanf("%d%d",&u,&v);
        if(u<=n1&&v<=m1)
        add(u+1,v+n1+1,1),
        add(v+n1+1,u+1,1);
    }
    for(int i=1;i<=m1;i++)
    {
        add(i+n1+1,n,1);//連右部點和彙點
        add(n,i+n1+1,1);
    }      

好啦完整代碼奉上：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int cnt=2;
int alist[6000001];
struct data{
    int v;int next;int value;
}edge[6000001];
void add(int u,int v,int value)
{
    edge[cnt].v=v;
    edge[cnt].value=value;
    edge[cnt].next=alist[u];
    alist[u]=cnt++;
    return ;
}
int h[1000001];
int q[1000001];
//dicnic暴力參見上面提到的部落格。
bool bfs()
{
    int x,next;
    memset(h,-1,sizeof(h));
    int head=0,tail=1;
    q[head]=1;
    h[1]=0;
    while(head<tail)
    {
        x=q[head++];
        next=alist[x];
        while(next)
        {
            int v=edge[next].v;
            int value=edge[next].value;
            if(value&&h[v]<0)
            {
                q[tail++]=v;
                h[v]=h[x]+1;
            }
            next=edge[next].next;
        }
    }
//    for(int i=1;i<=n*m;i++) printf("h[%d]=%d\n",i,h[i]);
    if(h[n]==-1) return false;
    return true;
}
int ans;
int dfs(int x,int y)
{
    if(x==n) return y;
    int next=alist[x];
    int w,used=0;
    while(next)
    {
        int v=edge[next].v;
        int value=edge[next].value;
        if(value&&h[v]==h[x]+1)
        {
                w=y-used;
                w=dfs(v,min(w,value));
                edge[next].value-=w;
                edge[next^1].value+=w;
                used+=w;
                if(used==y) return y;
        }
        next=edge[next].next;
    }
    if(!used) h[x]=-1;
    return used;
}
void dinic()
{
    while(bfs()) ans+=dfs(1,0x7fffffff);
}
int n1,m1,e1;
int main()
{
 //   freopen("testdata.in","r",stdin);
 //第一遍沒A就是因為忘了删上面這句話。。。
    scanf("%d%d%d",&n1,&m1,&e1);
    n=n1+m1+2;
    for(int i=1;i<=n1;i++)
    {
        add(1,i+1,1);
        add(i+1,1,1);
    }
    for(int i=1;i<=e1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        if(u<=n1&&v<=m1)
        add(u+1,v+n1+1,1),
        add(v+n1+1,u+1,1);
    }
    for(int i=1;i<=m1;i++)
    {
        add(i+n1+1,n,1);
        add(n,i+n1+1,1);
    }
    dinic();//暴力跑最大流
    printf("%d",ans);
    return 0;//程式拜拜
}      

好啦這道題就先這樣。對于要刷網絡流的大佬們要是想練一練怎麼見圖的話

P1402

是一個很好的選擇。

然後想深入學習的同學可以看看最小割和轉對偶圖。之後做一下

P4001