题目传送门:P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路 / Thought
关于二分图的最大匹配,参考以下文章:
算法学习笔记(5):匈牙利算法 - 知乎 (zhihu.com)
最大匹配的思路可以这么理解:dfs(x)函数是用于判断x能否在另一边占到坑位,如果能那就占着,如果已经有人了就看能不能让这人去别的地方,如果可以就占着,否则就不能,没有坑位可占。
需要一个vis数组并在每一次dfs前重置,use表示这个点被谁占了。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 509; vector<int> g[maxn], use(maxn); set<pair<int, int> > edges_st; bitset<maxn * 2> vis; bool dfs(int x)//表示是否能够占到坑位 { for(auto &i : g[x]) { if(!vis[i]) { vis[i] = true; if(!use[i] || dfs(use[i]))return use[i] = x, true; } } return false; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N, M, E;cin >> N >> M >> E; while(E --) { int x, y;cin >> x >> y; if(edges_st.count({x, y}))continue; g[x].push_back(y); edges_st.insert({x, y}); } int ans = 0; for(int i = 1;i <= N; ++ i) { vis.reset(); if(dfs(i))ans ++; } cout << ans << '\n'; return 0; }
Comments NOTHING