Luogu P3254 圆桌问题

傷城~ 2022-01-09 10:49 164阅读 0赞

#### [题目链接 \\(Click\\) \\(Here\\)][_Click_ _Here] ####

水题。记得记一下边的流量有没有跑完。

#include <bits/stdc++.h> using namespace std; const int N = 100010; const int M = 800010; const int INF = 0x3f3f3f3f; int cnt = -1, head[N]; struct egde { int nxt, to, f; }e[M]; void add_edge (int from, int to, int flw) { e[++cnt].nxt = head[from]; e[cnt].to = to; e[cnt].f = flw; head[from] = cnt; } void add_len (int u, int v, int f) { add_edge (u, v, f); add_edge (v, u, 0); } int n, m, sum, id[210][310], hav[N], tak[N]; int nd1 (int x) {return x;} int nd2 (int x) {return n + x;} queue <int> q; int cur[N], deep[N]; bool bfs (int s, int t) { memcpy (cur, head, sizeof (head)); memset (deep, 0x3f, sizeof (deep)); q.push (s); deep[s] = 0; while (!q.empty ()) { int u = q.front (); q.pop (); for (int i = head[u]; ~i; i = e[i].nxt) { int v = e[i].to; if (deep[v] == INF && e[i].f) { deep[v] = deep[u] + 1; q.push (v); } } } return deep[t] != INF; } int dfs (int u, int t, int lim) { if (u == t || !lim) { return lim; } int tmp = 0, flow = 0; for (int &i = cur[u]; ~i; i = e[i].nxt) { int v = e[i].to; if (deep[v] == deep[u] + 1) { tmp = dfs (v, t, min (lim, e[i].f)); lim -= tmp; flow += tmp; e[i ^ 0].f -= tmp; e[i ^ 1].f += tmp; if (!lim) break; } } return flow; } int main () { memset (head, -1, sizeof (head)); cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> hav[i]; sum += hav[i]; if (hav[i] > m) { puts ("0"); return 0; } } for (int i = 1; i <= m; ++i) { cin >> tak[i]; } int s = n + m + 1; int t = n + m + 2; for (int i = 1; i <= n; ++i) add_len (s, nd1 (i), hav[i]); for (int i = 1; i <= m; ++i) add_len (nd2 (i), t, tak[i]); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { id[i][j] = cnt + 1; add_len (nd1 (i), nd2 (j), 1); } } int max_flow = 0; while (bfs (s, t)) { max_flow += dfs (s, t, INF); } if (max_flow != sum) {puts ("0"); return 0;} puts ("1"); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (!e[id[i][j]].f) { printf ("%d ", j); } } printf ("\n"); } }

转载于:https://www.cnblogs.com/maomao9173/p/10479817.html

[_Click_ _Here]: https://www.luogu.org/problemnew/show/P3254