匈牙利算法

约 6 个字 52 行代码 预计阅读时间 1 分钟

讲课链接

题目

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxm = 1000050;
const int maxn = 1050;
struct node{
    int to, next;
}edge[maxm];
int flag[maxn][maxn];
int head[maxn], cnt;
inline void add(int u, int v){
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int id[maxn];// 每个女生他的原配是哪个男生
int vis[maxn];
inline int dfs(int now){ // 对于当前这个男生，是否能找到一个新的女生 增广路 
    for(int i = head[now];i;i = edge[i].next){
        if(!vis[edge[i].to]){
            vis[edge[i].to] = 1;
            if(!id[edge[i].to] || dfs(id[edge[i].to])){ // 或 有一个为真就为真 如果前面条件为真，那么后面条件就不会判断
                id[edge[i].to] = now;                   // 与 两个同时为真为真 如果前面条件为假，后面条件也不会判断
                return 1;
            }
        }
    }
    return 0;
}
inline int hungarian(int n){ // O(nm)
    int ans;
    for(int i = 1;i <= n;i++){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}
signed main(void){
    int n, m, e;
    scanf("%d %d %d", &n, &m, &e);
    int u, v;
    for(int i = 0;i < e;i++){
        scanf("%d %d",&u, &v);
        if(!flag[u][v])
        add(u, v),flag[u][v] = 1;
    }
    printf("%d", hungarian(n));
    return 0;
}