二分圖最大匹配及其各種各樣奇怪的概念與算法

收藏待读

二分圖最大匹配及其各種各樣奇怪的概念與算法

二分圖

對於一張圖中的點,可以分成兩組,其中,同一組內的點 互不相連 ,則我們成這張圖為二分圖

由此可得一些東西

  • 我們可以通過交叉染色判定二分圖,如果圖$G$是二分圖,則只需要 兩種 顏色來染色
  • 不含 奇數邊環的圖」就是二分圖

匹配

匹配是一張圖中一部分邊的集合,這個集合內的邊沒有 相交點

完美匹配

如果一個匹配中包含了這張圖內所有的點,我們就稱這個匹配為 完美匹配

最大匹配問題

給你一張圖,詢問這張圖的匹配最多包含多少個點,這個匹配被成為 最大匹配 ,這個問題被稱為 最大匹配問題

匈牙利算法

交替路

從未匹配點出發依次經過匹配邊與未匹配邊的路我們稱作交替路

增廣路

從為匹配點出發走交替路走到一個未匹配點的交替路我們稱其為增廣路

增廣路的非匹配邊定會比匹配邊多一條,故此我們可以通過查找增廣路來改進現有匹配,如果一個匹配已走不出增廣路那他就是最大匹配了

與最大匹配相關的定理

最小路徑覆蓋

點數 – 最大匹配數 = 最小路徑覆蓋

可謂是相當好理解了,如果有一個最小路徑覆蓋比當前少,則最大匹配一定會比當前多,那這還是最大匹配?

最小點覆蓋

最小點覆蓋 = 最大匹配數

詳見 : [ König定理 ]

代碼

// luogu-judger-enable-o2
#include 
#include 
using namespace std;

//edge start 
struct edge{
    int to,next;
}e[1100000];
int ehead[2100],ecnt;

inline void add(int now,int to){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}

int u,v;
int n,m,ee;
int ans;

bool vis[2100];
int cx[1100],cy[1100];

int dfs(int now){
    for(int i=ehead[now];i;i=e[i].next){
        if(!vis[e[i].to]){
            vis[e[i].to]=true;
            if(cy[e[i].to]==false||dfs(cy[e[i].to])){
                cx[now]=e[i].to;
                cy[e[i].to]=now;
                return true;
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d%d",&n,&m,&ee);
    for(int i=1;i<=ee;i++){
        scanf("%d%d",&u,&v);
        if(u<=n&&v<=m){
            add(u,v);
        }
    }
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        ans+=dfs(i);
    }       
    printf("%d",ans);
}

最大流方法

最大流也可以求解二分圖最大匹配

設二分圖中兩組互不相連接的點集中任意一個集合為$U$,另一個為$V$,然後

超級源點
超級匯點

別忘了反向邊

原文 : Woshiluo’s Notobook

相關閱讀

免责声明:本文内容来源于Woshiluo's Notobook,已注明原文出处和链接,文章观点不代表立场,如若侵犯到您的权益,或涉不实谣言,敬请向我们提出检举。