最大流例题
(T1) P2472 [SCOI2007]蜥蜴
- 提示 1：
最少的无法逃离的蜥蜴个数 = 总个数 - 最多的逃离的蜥蜴个数。 - 提示 2：
对于一个高度为 \(h\) 的石柱，意味着只能有至多 \(h\) 条蜥蜴经过这个石柱。这类似最大流中的流量限制。 - 正解：
考虑将平面图转为网络流图的形式，那么对于每一个石柱我们建立一个点，如果石柱 \(a\) 可以到达石柱 \(b\)，我们就让 \(a\to b\) 连接一条边，那么这条边允许通过无限的蜥蜴，所以流量限制 \(\infty\)。发现还有问题，就是如何保证每个石柱只通过 \(h_i\) 次，发现这和最大流中的流量限制一致，于是我们将每个石柱拆分为两个点，表示入点 \(u\)，和出点 \(u'\)，对于 \(a\xrightarrow \infty b\) 的边我们改成 \(a'\xrightarrow \infty b\)，就表示从 \(a\) 的出点到达 \(b\) 的入点，并且如果想要继续走，必须需要从 \(b\) 继续到达 \(b'\) 才可以，于是我们连接一条 \(b\xrightarrow {h_b} b'\) 的边即可限制走过 \(b\) 这个点的蜥蜴数量了，然后我们建立源点 \(S\)，连向每一个有蜥蜴的石柱，流量限制为 \(1\)，每一个可以到达边界外的石柱我们连向一条到达汇点 \(T\) 的边，流量无限。跑一边网络流即可求出最多可以逃走的蜥蜴个数，拿总蜥蜴个数减去最大流即为答案。
最小割
定义：
对于一张网络流图，每一条边的边权为其流量限制，考虑割掉一些边使得 \(S\) 与 \(T\) 不连通，最小边权和即为最小割。
定理：
\[最小割=最大流 \]证明：
- 最大流 \(\leq\) 最小割
首先根据割的定义，所有的流都必然经过割边集中的某一条边，那么流量总和最大就是割边集总和。
- 最大流 \(\geq\) 最小割
考虑我们求出了一个最大流，那么某些边会成为瓶颈，即残量网络上为 \(0\)。
这些边一定分布成为一个割，否则仍然会有增广路。
(T2) BZOJ P9304 Pku2125 Destroying The Graph
- 提示 1：
每一条边，要么它的入点删除出边，要么它的出点删除入边。 - Case 1：
对于这种 \(a,b\) 二选一的情况，容易想到，在网络流中的建图可以是这样的：
\(S\xrightarrow a x \xrightarrow b T\)，即串联关系。
那么考虑对于每一个点都建立一个点 \(i\)，连接两条边 \(S\xrightarrow {a_i} i\)，\(i\xrightarrow{b_i} T\)，每一条边 \(u\to v\)，那么我们让 \(u,v\) 之间连接一条 \(\infty\)，那么这条无限的边肯定不能割掉，于是我们一定是让 \(a_u,b_v\) 两条边割掉其中之一。这样建图是否有正确性？ - 正解：
这样建图，考虑这样的流量：\(S\xrightarrow{a_i} i\xrightarrow {b_i} T\)，这不就表示 \(a_i,b_i\) 必须割掉其中一个吗？
可是原题中并没有这样的限制。如何解决呢。
拆点，我们对于每一个点 \(i\)，拆成两个点 \(i,i'\)，对于原先的 \(u\to v\) 的边，我们改为 \(u\xrightarrow{\infty} v'\)，这样就相当于将 \(i\) 拆开，而原图相当于默认了一条 \(i\to i\) 的自环的边。
最后的建图就长这样：
最大权闭合子图
闭合子图：
对于一张 DAG（有向无环图）的某个子图，满足一下条件：
- 子图内的点，可以达到的点也一定在子图内。
最大权闭合子图：
点有点权，所有闭合子图中点权和最大的闭合子图。
最小割求最大权闭合子图
首先容易发先闭合子图有一个限制：
对于一个 DAG 中的某个点，如果要将其加入点集内，一定要满足其可达到的点也一定要在点集内。
我们要使最后使得点集内的点权最大化。
也就是说要让点集外的点权和最小化。
首先如果所有点权为正，那么整张图就是最大权闭合子图。
那么我们假设最开始将所有点权为正的点都选上。记点权和为 \(sum\)。
我们对于 DAG 上的每一个点，对应网络流上建一个点，如果这个点的点权为正
则连一条 \(S\xrightarrow {val_i} i\)，否则如果点权为负，我们连一条 \(i\xrightarrow{|val_i|} T\)，那么割掉一条 \(S\to i\) 的边就表示这个正点权的点我们不选了，割掉一条 \(i\to T\) 的边，就表示这个为负点权的点我们选进来了。
对于原图 DAG 上，有一条 \(u\to v\) 的边，就表示如果要选择 \(u\)，则 \(v\) 就一定需要选进来，那么我们在网络流图中连接一条 \(u\xrightarrow{\infty}{v}\) 即可。
那么这样的图为什么是对的？
考虑 \(val_u,val_v\) 的正负号，我们分类讨论：
- \(u:\)
+，\(v:\)-
那么网络流中就有一条这样的路径 \(S\xrightarrow {val_u} u \xrightarrow {\infty} v\xrightarrow {val_v} T\)，也就是说 \(u\) 选了，但是 \(v\) 没有选的情况是不允许出现的。
所以我们要么将 \(u\) 删去，要么将 \(v\) 选进来。
对于同号情况我们看以下例题，所以我们这么建图跑最小割，再用 \(sum\) 减去最小割就是最大权闭合子图的权值了。
(T3) 洛谷 P3872 [TJOI2010] 电影迷
考虑正点权连向 \(S\)，负点权连向 \(T\)，然后假设最开始所有的正点权全都选上，那么割掉正点权的边就表示删掉这个点，割掉负点权的边就表示选上这个点，于是对于 \(x,y\) 我们直接连接一条边 \(x\xrightarrow{d}y\)，考虑为什么是对的。
+-：
意味这如果一个正的选了，负的没选，那么就需要额外的 \(d\) 的代价。++：
考虑这样的情况：
如果直接删除 \(x\)，或者删除 \(y\) 都是没有问题的，那么问题是删除 \(a\) 之后，会不会有不删除 \(c,b\)，而去删除 \(x,y\) 的情况呢？是没有的，因为如果删除了 \(x\) 或 \(y\)，显然 \(a\) 是没有必要删除的。
感性理解。
最小费用最大流
就是在最大流的基础上多了，每一条边，每流一单位流量，需要一定的费用，然后需要在最大流的前提下，最小费用。
其实就是将 dinic 中的 bfs 改成 spfa，边权就是费用。。
代码：
const int V = 162243;
const int E = 432216;
const int inf = 1<<30;// ll inf = 1ll<<59;
template <class T>
struct CostGraph {
int s, t, size, etot;
T dis[V], cost = 0;
int head[V], cur[V];
bool vis[V];
struct edge {
int v, nxt, w, cost;
} e[E];
void init(int _s, int _t, int n) {
s = _s, t = _t, size = n;
etot = cost = 0;
fill(head, head + 1 + size, -1);
}
inline void add(int u, int v, int w, int o) {
e[etot] = {v, head[u], w, o}; head[u] = etot++;
e[etot] = {u, head[v], 0, -o}; head[v] = etot++;
}
bool spfa() {
rep(i,0,size) {
dis[i] = inf;
cur[i] = head[i];
vis[i] = false;
}
queue<int> q;
q.push(s); dis[s] = 0;
vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = false;
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (e[i].w && dis[v] > dis[u] + e[i].cost) {
dis[v] = dis[u] + e[i].cost;
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
return dis[t] != inf;
}
T dfs(int u, T m) {
if (u == t) return m;
T flow = 0;
vis[u] = true;
for (int &i = cur[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (!vis[v] && e[i].w && dis[v] == dis[u] + e[i].cost) {
T f = dfs(v, min(m, (T)e[i].w));
cost += f * e[i].cost;
e[i].w -= f;
e[i ^ 1].w += f;
m -= f;
flow += f;
if (!m) break;
}
}
if (flow) vis[u] = false;
return flow;
}
T dinic() {
T res = 0;
while (spfa()) res += dfs(s, inf);
return res;
}
};
(T4) P4016 负载平衡问题
我们对于每一个仓库建一个点 \(i\)，然后将它们按照题意连成一个环（相邻两个，\(n\to 1\)），然后源点 \(S \xrightarrow {a_i} i\)，\(i\xrightarrow{\overline{a}}T\)，跑一边最小费用最大流即可。
(T5) 洛谷 数字梯形问题
- 路径互不相交，我们对于每个点拆点，然后点限制流量为 1 即可
- 可以在节点处相交，将拆点之间的边流量限制改为 \(\infty\) （本质上等于没拆）。
- 最后一问，就将边的流量改成 \(\infty\) 即可，当然，如果您很无聊，可以选择做 \(m\) 遍 DP。
最后注意，这一题是求最大费用，所以跑最大费用最大流（就是最小费用将边权取相反数即可）。