P2319 [HNOI2006] 超级英雄
大意
\(m\) 对关系 \((u, v)\)，第 \(i\) 对表示 \(i\) 这个点可以选择 \(u\) 或 \(v\)。求最大的选择题数的方案数和方案。
（如果一道题做不出来就无法进行下一道题目）
思路
考虑二分图最大匹配。
实则并不算最大匹配，我们通过读题可以发现其实就是二分图匹配的过程，每次找一条增广路，如果找不到了，就说明当前无法继续进行这个游戏了。
也就是在匹配的过程中记录答案，如果找不到增广路径，那就直接 break 即可。
代码
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;const int MAXN = 1e3 + 5;
int n, m;
int mac[MAXN], ans[MAXN];
bool vis[MAXN];
vector<int> g[MAXN];bool dfs(int u){for(int &v : g[u]){if(!vis[v]){vis[v] = 1;if(mac[v] == -1 || dfs(mac[v])){ans[u] = v;mac[v] = u;return true;}}}return false;
}int hungary(int n){int cnt = 0;for(int i = 1;i <= m;i ++){memset(vis, 0, sizeof(vis));if(dfs(i)){cnt += 1;}else{return cnt;}}return cnt;
}int main(){cin >> n >> m;for(int i = 1;i <= m;i ++){int u, v; cin >> u >> v;g[i].push_back(u);g[i].push_back(v);}memset(mac, -1, sizeof(mac));int cnt = hungary(n);cout << cnt << '\n';for(int i = 1;i <= cnt;i ++){cout << ans[i] << '\n';}return 0;
}