本文共 1190 字，大约阅读时间需要 3 分钟。
给一个有向图，求最大匹配。
有相图的最大匹配，可以通过加上反向边， 求这个无向图的最大匹配，
原图的最大匹配就是无向图的最大匹配除2.
详细解释：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 5e3+10;int Next[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};vector G[MAXN];int Link[MAXN], Vis[MAXN];int n, m, k;bool Dfs(int x){ for (int i = 0;i < G[x].size();i++) { int node = G[x][i]; if (Vis[node] == 0) { Vis[node] = 1; if (Link[node] == -1 || Dfs(Link[node])) { Link[node] = x; return true; } } } return false;}int Solve(){ memset(Link, -1, sizeof(Link)); int cnt = 0; for (int i = 1;i <= n;i++) { memset(Vis, 0, sizeof(Vis)); if (Dfs(i)) cnt++; } return cnt;}int main(){ int t; scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1;i <= n;i++) G[i].clear(); int l, r; for (int i = 1;i <= 3*n/2;i++) { scanf("%d%d", &l, &r); G[l].push_back(r); G[r].push_back(l); } int cnt = Solve(); printf("%d\n", cnt/2); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10872085.html