二分图匹配模板洛谷P3386

题目链接：https://www.luogu.org/problem/P3386

题意：最裸不过的二分图匹配了，输入n,m,e，二分图的顶点个数分别是n,m，有e条边，之后e行每行u,v表示u,v之间有一条边（n,m<=1000）

注意：用的是匈牙利算法，时间复杂度为O(nm)，要用邻接矩阵求，不能用邻接表(时间复杂度会变为O(nmm))

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=1100;
#define meminf(a) memset(a,0x3f,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a));
int g[maxn][maxn];
bool vis[maxn];//vis数组是为了表示在这次遍历中这个妹子已经被访问过了，不再访问，以免陷入死循环 
int girl[maxn];
int n,m,e;
bool find(int x){
    for(int i=1;i<=m;i++){
        if(g[x][i]&&vis[i]==false){
            vis[i]=1;
            if(girl[i]==0||find(girl[i])){
                girl[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=0;i<e;i++){
        int a,b;scanf("%d%d",&a,&b);
        if(a>m||b>n) continue;//数据的锅，忽视 
        g[a][b]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        mem0(vis);
        if(find(i)) ans++;
    }
    printf("%d
",ans);
    return 0;
}

二分图匹配模板 洛谷P3386

相关推荐

二分图匹配模板洛谷P3386