Luogu1402 酒店之王

小灰灰 2021-12-20 10:29 165阅读 0赞

[Luogu1402 酒店之王][Luogu1402]

> 有 \\(n\\) 个 \\(A\\) 类节点， \\(p\\) 个 \\(B\\) 类节点， \\(q\\) 个 \\(C\\) 类节点。每个 \\(A\\) 与一个 \\(B\\) 和一个 \\(C\\) 构成一组匹配（每个 \\(A\\) 只能与给定的 \\(B\\) 、 \\(C\\) 匹配，且每个 \\(B\\) 、 \\(C\\)只能匹配一个 \\(A\\) ），求最大匹配数。
> 
> \\(n,\\ p,\\ q\\leq100\\)

网络流

--------------------

先建成 \\(B\\to A,\\ A\\to C\\) 两个二分图匹配，然后中间每个 \\(A\\) 类节点拆点限制流量并继承。

代码

#include <bits/stdc++.h> using namespace std; const int maxn = 410, maxm = 1e5 + 10, inf = INT_MAX; int N, k1, k2; int S, T, h[maxn], q[maxn], dis[maxn], cur[maxn]; struct edges { int nxt, to, w; edges(int x = 0, int y = 0, int z = 0) : nxt(x), to(y), w(z) {} } e[maxm]; void addline(int u, int v, int w) { static int cnt = 1; e[++cnt] = edges(h[u], v, w), h[u] = cnt; e[++cnt] = edges(h[v], u, 0), h[v] = cnt; } bool bfs() { memcpy(cur, h, sizeof h); memset(dis, -1, sizeof dis); int l = 1, r = 1; q[1] = S, dis[S] = 0; while (l <= r) { int u = q[l++]; for (int i = h[u]; i; i = e[i].nxt) { int v = e[i].to; if (dis[v] == -1 && e[i].w) { q[++r] = v, dis[v] = dis[u] + 1; if (v == T) return 1; } } } return 0; } int dfs(int u, int f) { if (u == T || !f) { return f; } int res = 0, tmp; for (int& i = cur[u]; i && f; i = e[i].nxt) { int v = e[i].to; if (dis[v] == dis[u] + 1 && e[i].w) { if (!(tmp = dfs(v, min(f, e[i].w)))) { dis[v] = 0; continue; } e[i].w -= tmp, e[i ^ 1].w += tmp, res += tmp, f -= tmp; } } return res; } int dinic() { int res = 0; while (bfs()) { res += dfs(S, inf); } return res; } int main() { scanf("%d %d %d", &N, &k1, &k2); S = N + N + k1 + k2 + 1, T = S + 1; for (int i = 1; i <= k1; i++) { addline(S, i, 1); } for (int i = 1; i <= k2; i++) { addline(N + N + k1 + i, T, 1); } for (int i = 1; i <= N; i++) { addline(k1 + i, N + k1 + i, 1); } for (int i = 1; i <= N; i++) { for (int j = 1, x; j <= k1; j++) { scanf("%d", &x); if (x) addline(j, k1 + i, 1); } } for (int i = 1; i <= N; i++) { for (int j = 1, x; j <= k2; j++) { scanf("%d", &x); if (x) addline(N + k1 + i, N + N + k1 + j, 1); } } printf("%d", dinic()); return 0; }

转载于:https://www.cnblogs.com/Juanzhang/p/10549544.html

[Luogu1402]: https://www.luogu.org/problemnew/show/P1402