先对原图跑一遍匈牙利得到原始最大匹配，再遍历每个出度>1的点，考虑若新加入点，能否找到增广路，若可行则答案对应增加
代码：
#include#include #include #include #include #include using namespace std;typedef long long ll;const int MAX_V = 2000;const int MAX_E = 80000;struct Hungary { struct Edge { int to, next; } es[MAX_E]; int head[MAX_V]; int V, E, match[MAX_V]; bool vis[MAX_V]; void init(int V) { this->V = V; this->E = 0; memset(head, -1, sizeof head); } void addEdge(int u, int v) { es[E].to = v; es[E].next = head[u]; head[u] = E++; } bool dfs(int u) { vis[u] = true; for (int i = head[u]; i != -1; i = es[i].next) { int v = es[i].to, w = match[v]; if (w < 0 || !vis[w] && dfs(w)) { match[v] = u; return true; } } return false; } int maxMatch() { int res = 0; memset(match, -1, sizeof match); for (int u = 0; u < V; u++) { memset(vis, false, sizeof vis); if (dfs(u)) { res++; } } return res; }} hun;int main() { int m, n, k, out[2000] = { 0 }, match[2000] = { 0 }; scanf("%d%d%d", &m, &n, &k); hun.init(m); for (int i = 0; i < k; i++) { int u, v; scanf("%d%d", &u, &v); hun.addEdge(u - 1, v - 1); out[u - 1]++; } int res = hun.maxMatch(); int ans = res; memcpy(match, hun.match, sizeof hun.match); for (int u = 0; u < m; u++) { if (out[u] > 1) { memcpy(hun.match, match, sizeof match); int cnt = 0; for (int j = 0; j < 2; j++) { hun.head[m + j] = -1; for (int i = hun.head[u]; ~i; i = hun.es[i].next) { int v = hun.es[i].to; hun.addEdge(m + j, v); cnt++; } } hun.E -= cnt; int extra = 0; for (int j = 0; j < 2; j++) { memset(hun.vis, 0, sizeof hun.vis); if (hun.dfs(m + j)) { extra++; } } ans = max(ans, res + extra); } } printf("%d\n", ans);}