二分图的最大匹配——匈牙利算法
作者:
zhangas2
,
2024-03-16 10:26:01
,
所有人可见
,
阅读 9
#include<bits/stdc++.h>
//unordered_map hash
//priority_queue<int,vector<int>,greater<int>>
//deque front和back
#define endl '\n'
#define PII pair<int,int>
//#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;}
int n1, n2, m;
vector<int> g[505];
int match[505];
int st[505];
int find(int u){
for(auto &v : g[u]){
if(st[v]) continue;
st[v] = 1;
if(!match[v] || find(match[v])){
match[v] = u;
return 1;
}
}
return 0;
}
signed main(){
n1 = read(), n2 = read(), m = read();
for(int i = 1; i <= m; ++ i){
int u = read(), v = read();
g[u].push_back(v);
}
int ans = 0;
for(int i = 1; i <= n1; ++ i){
memset(st, 0, sizeof(st));
if(find(i)) ++ ans;
}
cout << ans;
return 0;
}