匈牙利算法优化

pengyulun · 2025-11-09 10:24:58 · 个人记录

#include <bits/stdc++.h>
using namespace std;
const int N=505,M=5e4+8;
struct G{int x,t;} a[M];
int n,m,e,w[N],h[N],cnt=0,k[N];
bool dfs(int x){
    w[x]=1;
    for (int i=h[x],j=0;i;j=i,i=a[i].t){
            if (k[a[i].x]==0||(w[k[a[i].x]]==0&&dfs(k[a[i].x]))){
            k[a[i].x]=x;w[x]=0;return 1;
        }else if (w[k[a[i].x]]==2){
            if (j==0) h[x]=a[i].t;
            else a[j].t=a[i].t;
        }
    }
    w[x]=2;
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >>n>>m>>e;
    for (int i=1,x,y;i<=e;++i){
        cin >>x>>y;
        a[++cnt]={y,h[x]},h[x]=cnt;
    }
    int ans=0;
    for (int i=1;i<=n;++i){
        if (dfs(i)) ++ans;
    }
    cout <<ans;
    return 0;
}