P3163 [CQOI2014] 危桥 题解

· · 题解

思路

首先最优方案肯定是走一条路然后原路返回。

首先考虑 a_1,a_2，用 path(a,b) 表示最优的 a_1\to a_2\to a_1 路径，分两种情况证明：

  1. 若 path(a_1,a_2) 不包含危桥。

    显然原路返回最优，因为走其他路可能占用危桥的使用次数。

  2. 若 path(a_1,a_2) 包含危桥，令其中一座危桥为 (x,y)。

    若走一条不经过 (x,y) 的路，必然会经过另一座危桥（否则 path(a_1,a_2) 就不是最优路径），令其为 (x_1,y_1)，这样会使 (x,y),(x_1,y_1) 都被经过一次，这样要么导致 b_1\to b_2\to b_1 走不通，要么导致 path(b_1,b_2) 也不能原路返回，要么只能与 path(a_1,a_2) 交叉。

    因此，绕路走严格不优于原路返回。

因此可以直接将危桥作为一条边权为 $1$ 的边，普通桥作为一条边权为 $+\infty$ 的边，建立源点 $s$ 和汇点 $t$，连边 $(s,a_1,a_n),(a_2,t,a_n),(s,b_1,b_n),(b_2,t,b_n)$，判断最大流是否为 $a_n+b_n$。 但这样可能会流 $a_1\to b_2,b_1\to a_2$，不足以判断是否合法。 考虑到控制流的起点较为困难，因此需要一种玄学的方法来判断。 先放结论： > 若上文建图方法跑出的最大流为 $a_n+b_n$，且将边 $(s,b_1,b_n),(b_2,t,b_n)$，替换为 $(s,b_2,b_n),(b_1,t,b_n)$ 后最大流也为 $a_n+b_n$，该组数据合法。 接下来证明该结论的的充要性。 以下图为例： ![](https://cdn.luogu.com.cn/upload/image_hosting/p49p2zy0.png) 令 $f(x,y)$ 表示 $x$ 到 $y$ 的流量，假设该图最大流为 $a_n+b_n$，将边 $(s,b_1),(b_2,t)$，替换为 $(s,b_2),(b_1,t)$ 后最大流也为 $a_n+b_n$，有： $$\begin{aligned} &\because f(a_1,b_1)=f(a_1,b_2)\\ &\therefore x=y+z\\ &\because z\ge x,y\ge 0\\ &\therefore x=y=0\\ &\therefore f(a_1,a_2)=a_n,f(b_1,b_2)=b_n \end{aligned}$$ 因此结论成立。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int n, s, t, a1, a2, an, b1, b2, bn, idx, d[55], v[5005], h[55], e[5005], ne[5005], st[55]; char g[55][55]; queue<int> q; void add(int x, int y, int z) { v[++idx] = y, e[idx] = z, ne[idx] = h[x], h[x] = idx; v[++idx] = x, ne[idx] = h[y], h[y] = idx; } bool bfs() { for (int i = 1; i <= t; i++) d[i] = 0, st[i] = h[i]; d[s] = 1, q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = h[x]; ~i; i = ne[i]) { int y = v[i]; if (!d[y] && e[i]) { d[y] = d[x] + 1; q.push(y); } } } return d[t]; } int dfs(int x, int flow) { if (x == t || !flow) return flow; int ret = 0, tmp; for (int i = st[x]; ~i; i = ne[i]) { int y = v[i]; st[x] = i; if (d[y] == d[x] + 1) { tmp = dfs(y, min(flow - ret, e[i])); ret += tmp; e[i] -= tmp; e[((i - 1) ^ 1) + 1] += tmp; } } return ret; } int dinic() { int ret = 0; while (bfs()) ret += dfs(s, 1e9); return ret; } void clear() { for (int i = 1; i <= t; i++) h[i] = st[i] = -1, d[i] = 0; for (int i = 1; i <= idx; i++) v[i] = e[i] = ne[i] = 0; idx = 0; } void build() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; if (g[i][j] == 'N') add(i, j, 1e9); else if (g[i][j] == 'O') add(i, j, 1); } } } int main() { memset(h, -1, sizeof h); while (~scanf("%d%d%d%d%d%d%d", &n, &a1, &a2, &an, &b1, &b2, &bn)) { a1++, a2++, b1++, b2++; s = n + 1, t = n + 2; for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1); build(); add(s, a1, an), add(a2, t, an); add(s, b1, bn), add(b2, t, bn); if (dinic() != an + bn) { puts("No"); clear(); continue; } clear(); build(); add(s, a1, an), add(a2, t, an); add(s, b2, bn), add(b1, t, bn); if (dinic() != an + bn) { puts("No"); clear(); continue; } puts("Yes"); clear(); } return 0; } ```