P3163 [CQOI2014] 危桥 题解
wxzzzz
2024-02-24 18:28:58
### 思路
首先最优方案肯定是走一条路然后原路返回。
首先考虑 $a_1,a_2$,用 $path(a,b)$ 表示最优的 $a_1\to a_2\to a_1$ 路径,分两种情况证明:
1. 若 $path(a_1,a_2)$ 不包含危桥。
显然原路返回最优,因为走其他路可能占用危桥的使用次数。
1. 若 $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)$ 交叉。
因此,绕路走严格不优于原路返回。
$path(b_1,b_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;
}
```