LOJ 6479 [ICPC World Finals 2017] 小小水管工 Son of Pipe Stream 题解

发表于 分类于 ， 阅读次数： Waline：
很有启发性的网络流题。

题意

原题链接

  • 给出 \(n\) 个城市和 \(m\) 条双向管道，以及两个实数 \(v\) 和 \(a\)。有两种液体，分别是水和 Flubber（下面简写为 W 和 F）。\(1\) 号和 \(2\) 号城市分别生产 Flubber 和水，并通过管道流入 \(3\) 号城市。对于一条管道，其中可以同时存在两种液体，但是方向必须相同。每条管道有一个容量 \(c_i\)，如果一条管道中有 \(w\) 个单位的水和 \(f\) 个单位的 Flubber，那么需要满足 \(v\cdot f + w \le c_i\)。记最终流到 \(3\) 号城市的水和 Flubber 分别为 \(W\) 和 \(F\)，求 \(F^a\cdot W^{1-a}\) 的最大值，并给出任意一个方案。
  • \(n \le 200\)，\(n - 1 \le m \le \frac{n(n - 1)}{2}\)，\(1\le v,c_i\le 10\)，\(0.01\le a\le 0.99\)。

英文题解

做法

首先 \(v\) 是没有用的，因为我们可以把所有的 Flubber 都乘上 \(v\)，最后把答案除以 \(v^a\)，这样就把 \(v\) 去掉了。

考虑如果我们不区分两种液体（即两个源点都可以产出两种液体），那么这就是一个普通最大流。设此时的流量为 \(Z\)。

现在考虑区分两种液体怎么做。
设两种液体的流量分别为 \(F\) 和 \(W\)，那么容易发现 \(F+W\le Z\)。那是不是 \(F\) 的取值范围就是 \([0, Z]\) 呢？
很容易发现这是错的。假设我们只保留 Flubber，设此时的最大流为 \(F_{\max}\)，类似地定义 \(W_{\max}\)，那么容易发现 \(F\) 的取值范围其实应该是 \([Z-W_{\max},F_{\max}]\)。

接下来就是人类智慧。感性理解一下我们能够发现，似乎对于任意一个 \(F\in [Z-W_{\max}, F_{\max}]\)，都存在一种方案使得 \(F+W=Z\)（我们先不考虑 Flubber 和水的方向不能相同的限制）。

证明

我们任取一个 \(F=F_{\max}\) 的方案，记为 \(\overrightarrow f\)；然后任取一个 \(W=W_{\max}\) 的方案，记为 \(\overrightarrow w\)。
因为在 \(\overrightarrow f\) 中 \(F=F_{\max}\)，而在 \(\overrightarrow w\) 中 \(F=Z-W_{\max}\)，而我们知道 \(F\in[Z-W_{\max}, F_{\max}]\)，所以必然存在实数 \(\alpha\in[0,1]\) 使得 \(\alpha F_{\max} + (1-\alpha)(Z-W_{\max}) = F\)，那么此时 \(\alpha\overrightarrow f+(1-\alpha)\overrightarrow w\) 就是流量为 \(F\) 的一个方案。

现在问题转化为，对于任意 \(F\) 满足 \(F\in[Z-W_{\max}, F_{\max}]\)，求 \(F^a\cdot (Z-F)^{1-a}\) 的最大值。简单求导发现应该取 \(F=a\cdot Z\)。如果 \(a\cdot Z\) 不在 \([Z-W_{\max}, F_{\max}]\) 内，就取区间内离 \(a\cdot Z\) 最近的点就好了。记这个点为 \(F^*\)，并记 \(Z-F^*=W^*\)。

求导过程

记 \(G(F) = F^a(Z-F)^{1-a}\)，那么

\[ \begin{aligned} &G'(F)\\ =&(F^a(Z-F)^{1-a})'\\ =&(F^a)'\cdot (Z-F)^{1-a}+((Z-F)^{1-a})'\cdot F^a\\ =&aF^{a-1}(Z-F)^{1-a}+(a-1)(Z-F)^{-a}F^a\\ =&F^{a-1}(Z-F)^{-a}(a(Z-F)+(a-1)F)\\ =&F^{a-1}(Z-F)^{-a}(aZ-F) \end{aligned} \]

因为 \(G(F)\) 在定义域内连续，所以极值点即为所有 \(G'(F)=0\) 的点，即 \(0,Z,aZ\) 三个点。代入原式发现 \(0,Z\) 都是最小值，所以最大值就是 \(F=aZ\)。

现在答案已经求出来了，但是还要构造方案。注意到我们一直没考虑水和 Flubber 的方向不能相反的限制，但其实这不影响，只要我们最终构造出来的方案满足这个限制就行了。
求方案其实也比较简单。首先我们给 \(1\) 号点限制 \(F^*\) 的流量，给 \(2\) 号点限制 \(W^*\) 的流量，跑一个最大流，这样可以求出最优解中每条边的方向和总流量。但是我们没法把 Flubber 和水区分开。
于是我们建一个新的图，点还是原图的点，但是边的方向和流量为最优解中这条边的方向和流量。那么这个图其实本来就是一个最大流。然后我们 只 给 \(1\) 号点 \(F^*\) 的流量，那么此时的最大流就是 Flubber 的方案。这样会不会导致水的方案出问题呢？其实不会，因为一个合法流减去它的子流还是一个合法流。而且这个方案也满足水和 Flubber 的方向不能相反的限制。

那么这道题就做完了，感觉难点在于这个结论和找方案。

代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>

const int N = 200 + 5;
const int M = N * N;
const int FLOW_N = N + 4;
const int FLOW_M = N * N * 2 + N + 2;
const double eps = 1e-8;
const double FINF = 1e18;

int n, m;
struct GraphEdge { int u, v; double w; } e[M];
double fe[M];
double V, A;

struct Dinic {
	struct Edge { int to, nxt; double r; } edge[FLOW_M << 1];
	int head[FLOW_N], cur[FLOW_N], ek;
	int n, s, t;
	int dep[FLOW_N];
	std::queue<int> q;
	void add_one_edge(int u, int v, double c) { edge[ek] = (Edge){v, head[u], c}, head[u] = ek++; }
	bool bfs() {
		for(int i = 1; i <= n; i++) dep[i] = 0;
		dep[s] = 1, q.push(s);
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int i = head[u]; i; i = edge[i].nxt) if(!dep[edge[i].to] && edge[i].r > eps) {
				int v = edge[i].to;
				dep[v] = dep[u] + 1;
				q.push(v);
			}
		}
		return dep[t];
	}
	double dfs(int u, double in) {
		if(u == t) return in;
		double out = 0;
		for(int &i = cur[u]; i; i = edge[i].nxt) if(dep[u] + 1 == dep[edge[i].to] && edge[i].r > eps) {
			int v = edge[i].to;
			double ret = dfs(v, std::min(in, edge[i].r));
			if(ret < eps) continue;
			edge[i].r -= ret, edge[i ^ 1].r += ret;
			in -= ret, out += ret;
			if(in < eps) return out;
		}
		if(out < eps) dep[u] = 0;
		return out;
	}
	Dinic() : ek(2) {}
	void init(int n_) { n = n_; ek = 2; for(int i = 1; i <= n; i++) head[i] = 0; }
	void add_edge(int u, int v, double c) { add_one_edge(u, v, c), add_one_edge(v, u, 0); }
	double maxflow(int s_, int t_) {
		s = s_, t = t_;
		double ret = 0;
		while(bfs()) {
			for(int i = 1; i <= n; i++) cur[i] = head[i];
			ret += dfs(s, FINF);
		}
		return ret;
	}
} dinic;

int main() {
	scanf("%d%d%lf%lf", &n, &m, &V, &A);
	for(int i = 1; i <= m; i++) scanf("%d%d%lf", &e[i].u, &e[i].v, &e[i].w);
	int src = n + 1, dst = n + 2;
	dinic.init(n + 2);
	for(int i = 1; i <= m; i++) dinic.add_edge(e[i].u, e[i].v, e[i].w), dinic.add_edge(e[i].v, e[i].u, e[i].w);
	dinic.add_edge(src, 2, FINF), dinic.add_edge(src, 1, FINF), dinic.add_edge(3, dst, FINF);
	double flow = dinic.maxflow(src, dst);
	dinic.init(n + 2);
	for(int i = 1; i <= m; i++) dinic.add_edge(e[i].u, e[i].v, e[i].w), dinic.add_edge(e[i].v, e[i].u, e[i].w);
	dinic.add_edge(src, 1, FINF), dinic.add_edge(3, dst, FINF);
	double Fmax = dinic.maxflow(src, dst);
	dinic.init(n + 2);
	for(int i = 1; i <= m; i++) dinic.add_edge(e[i].u, e[i].v, e[i].w), dinic.add_edge(e[i].v, e[i].u, e[i].w);
	dinic.add_edge(src, 2, FINF), dinic.add_edge(3, dst, FINF);
	double Wmax = dinic.maxflow(src, dst);
	double F = std::max(std::min(A * flow, Fmax), flow - Wmax);
	double W = flow - F;
	// printf("flow = %.3f, Fmax = %.3f, Wmax = %.3f, F = %.3f\n", flow, Fmax, Wmax, F);
	dinic.init(n + 2);
	for(int i = 1; i <= m; i++) dinic.add_edge(e[i].u, e[i].v, e[i].w), dinic.add_edge(e[i].v, e[i].u, e[i].w);
	dinic.add_edge(src, 2, W), dinic.add_edge(src, 1, F), dinic.add_edge(3, dst, FINF);
	double ff1 = dinic.maxflow(src, dst);
	assert(std::abs(ff1 - flow) <= eps);
	for(int i = 2; i <= 4 * m + 1; i += 4) fe[(i + 2) / 4] = dinic.edge[i ^ 1].r - dinic.edge[(i + 2) ^ 1].r;
	// for(int i = 1; i <= m; i++) printf("(%d, %d) %.4f\n", e[i].u, e[i].v, fe[i]);
	dinic.init(n + 2);
	for(int i = 1; i <= m; i++) dinic.add_edge(e[i].u, e[i].v, std::max(fe[i], 0.)), dinic.add_edge(e[i].v, e[i].u, std::max(-fe[i], 0.));
	dinic.add_edge(src, 1, F), dinic.add_edge(3, dst, FINF);
	double ff2 = dinic.maxflow(src, dst);
	// printf("ff = %.3f\n", ff2);
	assert(std::abs(ff2 - F) <= eps);
	for(int i = 2; i <= 4 * m + 1; i += 4) {
		double f = dinic.edge[i ^ 1].r - dinic.edge[(i + 2) ^ 1].r;
		printf("%.11f %.11f\n", f / V, fe[(i + 2) / 4] - f);
	}
	printf("%.11f\n", pow(F / V, A) * pow(flow - F, 1 - A));
	return 0;
}

参考资料

https://www.csc.kth.se/~austrin/icpc/finals2017solutions.pdf
https://cekavis.github.io/icpc-world-finals-2017/