正文
p3386 二分图匹配模板
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
https://www.luogu.org/problemnew/show/P3386
可以只做一边的匹配
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + ;
vector<int> G[maxN];
int match[maxN];
int vis[maxN];
int n, m, e, sum;
int dfs(int u) { for(int i = ; i < G[u].size(); i++) {
int v = G[u][i];
//有路而且没被访问
if(!vis[v]) {
vis[v] = ;//标记点i已经访问过 //如果点i未被配对或者找到了新的配对
if(match[v] == || dfs(match[v])) {
//更新配对关系
match[v] = u;
return ;
}
}
}
return ;
} int main() {
// freopen("testdata.in","r", stdin);
scanf("%d %d %d", &n, &m, &e);
for(int i = ; i < e; i++) {
int u, v;
scanf("%d %d", &u, &v);
if(u > n || v > m) continue; //u总是在左边, 只做u的匹配
// v += 10000;
G[u].push_back(v);//只做一边建单向边
// G[v].push_back(u);
} memset(match, , sizeof(match)); for(int i = ; i <= n; i++){
memset(vis, , sizeof(vis));
if(dfs(i)) {
sum++;
}
}
printf("%d\n", sum); }