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

二分图匹配

2024-10-07 06:23:39   215人阅读

二分图是这样一种图：假设我们有一张图，把它拦腰切一刀，切成两段，每一段的所有节点没有连边。

技术分享请看一个典型的二分图。观察可以得到，左面的三个节点属于同一侧，它们没有连边；右面的四个节点也属于一侧，它们没有连边。

 

这就是二分图。 撒花完结

 

所谓二分图的最大匹配，就是指对于一个二分图，通过取舍某些边让它的节点两两匹配数达到最大。换句话说，就是搞出最多的一一对应。
用匈牙利算法，dfs遍历图。如果发现dfs到的点以前没有遍历过，则检查：

　　如果目标还没有跟别人匹配或它的搭档已经跟别人匹配了，则目标跟起始点匹配，并让答案数+1.反之则不变。

 

放题放代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#define size 1010
bool vis[size];
int link[size];
bool mp[size][size];
int n,m,e;
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch==‘-‘)    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=(num<<1)+(num<<3)+ch-‘0‘;
        ch=getchar();
    }
    return num*f;
}

bool dfs(int x){
    for(int i=1;i<=m;++i){
        if(mp[x][i]&&!vis[i]){
            vis[i]=1;
            if(!link[i]||dfs(link[i])){    link[i]=x;    return 1;    }
        }
    }
    return 0;
}




int ans;
int main(){
    
    n=read(),m=read(),e=read();
    int from,to;
    for(int i=1;i<=e;++i){
        from=read();to=read();
        mp[from][to]=1;
    }
    for(int i=1;i<=n;++i){
        memset(vis,0,sizeof(vis));
        if(dfs(i))    ans++;
    }
    printf("%d",ans);
    return 0;
}

 

二分图匹配


联系
我们