最近在做网络流的题目，接下来说几个我做到感觉有点意思题目。网络流问题其实全是模板，但是难就难在如何把问题抽象成网络流模型。

T1 - 狼抓兔子

题目传送门

我是觉得这题的题面很史所以放过来。题目让我们求在能一网打尽的前提下，设置尽可能少的狼。这个所谓的一网打尽，其实是指我们选中一些边以后，不论 $S$ 到 $T$ 怎么走，都必须经过我们选中的边。如果了解了这个，那么就是模板的最小割了（你怎么知道我一开始没看懂在网上查了一圈题解全都是“一眼模板”）

T2 - 蜥蜴

题目传送门

这题是一道经典的拆点题。因为石柱是有高度的，这个高度相当于是一个限制，所以说我们很容易就可以想到把一个石柱拆为两个点：一个称为石柱的顶端，一个称为石柱的底端。

那么我们可以这样理解题目中的几类操作：

  1. 放蜥蜴：建立超级源点 $S$，对于任意有蜥蜴的石柱，建立从 $S$ 到这个石柱顶端容量为 $1$ 的边。容量为 $1$ 是因为这个点只有一只蜥蜴，所以我们放也只能放一只。
  2. 石柱：对于每一个有高度的石柱，从石柱顶端连接到石柱底端，容量为高度。这样的话从这个石柱通过的蜥蜴数量就有了限制。
  3. 石柱互通：对于任意一对能够互相抵达的石柱，从出发石柱的底端连接到目的石柱顶端，容量为 INF，因为题目并没有限制跳跃的次数。连边的逻辑是我们观察上一个的定义，我们如果要离开某一个石柱，按照上一条的定义只能从底端离开，不然的话就不会记录跳跃所消耗的高度。
  4. 蜥蜴离开：建立超级汇点 $T$，对于任意能够跳到场地外石柱，从石柱的底端连接到 $T$，容量为 INF，因为并没有说每个石柱只能离开固定数量的蜥蜴，如果流量还够的话，他自然可以走到石柱底端，也自然可以离开了。

用这个思路建图即可。另外有一个注意事项，就是石柱互通的图的时候，不要尝试像下面这样枚举，你会挂的。因为你漏建了 i<i2,j>j2 和 i>i2,j<j2 这一类的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
        for(int i2 = i + 1; i2 <= n; i2++) {
            for(int j2 = j + 1; j2 <= m; j2++) {
                if(!canJump(i, j, i2, j2)) continue;
                G.AddEdge(id(i, j) ^ 1, id(i2, j2), 0, INF);
                G.AddEdge(id(i2, j2), id(i, j) ^ 1, 0, 0);
                G.AddEdge(id(i2, j2) ^ 1, id(i, j), 0, INF);
                G.AddEdge(id(i, j), id(i2, j2) ^ 1, 0, 0);
            }
        }
    }
}

T3 - The Great Wall I

这题好像提交不了了，老师上课讲过，觉得挺有意思。题号是 ZOJ-3475。

题目的意思很简单，建立一个长城，使得 X 点和 E 点隔开（ E 经过任意联通的格子都无法到达 X ）然后呢，网格上又有一些盟国 A，数量不超过 $5$，在格子的某一边上修建长城有花费，如果盟国也在长城的庇护下可以减小花费，问给出一个能隔开 X 和 E 点的最优方案。

注意到盟国的数量很少，复杂度一定和盟国有关，显然这个数据范围和盟国有关的的复杂度一定是指数级的。所以不难想到枚举让我们的长城庇护哪些盟国。对于盟国和 X 点，都从源点引出一条边与他们相连，容量为 INF，然后对于两个相邻的格子，连边，容量是他们相邻的边的代价。另外边界外的点也要连接到汇点。然后对于每一组这个信息求最小割（最大流）即可。

很有意思的题，这个题目其实要想到这个构造挺难的。

T4 - 上下界

题目传送门

这题是无源汇上下界可行流的模板题，由于之前没有写过，所以说放在这里讲。

这个模型的大致意思是，现在对于一个网络，每一条边出了容量的上限还有下限，问有没有一种可行的流，使得这个网络上任意一点的流入流量等于流出流量。

显然这需要模型转化，如何把这个问题转化为我们平时做的最大流呢？不难，直观的想法就是先忽略下限，然后通过一些手段来使得答案变成对的。

那么我们首先确立几个概念：

  1. 自由流量：上限减去下限，这一部分流量可以自由分配
  2. 下界流量：下限所规定至少要分配的流量

那么我们忽视了下界流以后，就需要对于这个点修正。因为原来的下界流量可以认为是进入这个点的下界流和离开这个点的下界流之差，所以说这个少计算的流量我们就可以通过建立一个超级源点来发送，直接连到这个点，让流量为这个差值。

设 $M$ 为这个点流入流量与流出流量的差值，那么：

  1. $M = 0$，无事发生
  2. $M>0$，流入量过大，建立超级源点 $S$ 连接该点，容量为 $M$。
  3. $M<0$，流出量过大，建立超级汇点 $T$ 被该点连接，容量为 $|M|$ 即 $-M$。

这样建立以后，我们跑最大流，如果源点出发的几条边都满流了，就说明可行。因为源点发出的流量和汇点接受的流量是守恒的，如果这些修正的流量全部满流，说明全部修正正确，当然是可行流了。

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
// example code by deepseek
function NoSourceSinkFeasibleFlow(n, edges):
    // 初始化
    S = n, T = n+1
    A = array of size n, filled with 0
    new_edges = []
    
    // Step 1: 构造辅助图并计算净流量
    for each (u, v, l, r) in edges:
        A[u] -= l
        A[v] += l
        add_edge(u, v, r - l)  // 添加容量为r-l的边到新图
        record edge position
    
    // Step 2: 添加超级源汇边
    sum_positive = 0
    for u in 0..n-1:
        if A[u] > 0:
            add_edge(S, u, A[u])
            sum_positive += A[u]
        elif A[u] < 0:
            add_edge(u, T, -A[u])
    
    // Step 3: 判断满流
    max_flow = compute_max_flow(S, T)
    if max_flow != sum_positive:
        return "无解"
    
    // Step 4: 恢复实际流量
    feasible_flow = []
    for each original edge (u, v, l, r):
        feasible_flow.append(l + residual_flow_on_reverse_edge)
    return feasible_flow

T5 - Budget

题目传送门

首先题目意思是：给出一个 $n\times m$ 的矩阵，输入每一行的和，每一列的和。另外输入一些形如 x y > z 的限制条件代表第 $x$ 行第 $y$ 列的元素必须大于 $z$，其中不等号可以替换为 $\{<,=,>\}$。特别的，当 $x$ 或者 $y$ 为 $0$ 的时候，表示所有行或者所有列。问是否存在一个满足要求的矩阵，若存在，输出对应矩阵，若不存在，输出 IMPOSSIBLE。

这题是有源汇上下界可行流的模板题。这样来建立一个上下界网络：

  1. 建立源点 $S$ 向每一行连边，上下界均为行和
  2. 建立汇点 $T$ 向每一列连边，上下界均为列和
  3. 对于任意一点 $(x,y)$ 建立 $x\rightarrow y$ 的边，上下界就是题目给出的上下界（这里可以判断是否有非法的上下界即下界高于上界，这样显然非法）

这样以后我们要如何解决他呢？还是一样的，转化问题，要把有源汇转化为无源汇，这样我们就再次可以解决问题了，那么如何转化就成了问题。

与无源汇不同的是，我们的网络变得有源汇，所以说我们直接从汇点 $T$ 连向源点 $S$，容量为 INF，这样就保证了网络的循环性质，就变得无源汇了。

然后在此基础上建立超级源汇点 $SS,TT$，重复无源汇的修正操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// example code by deepseek
function WithSourceSinkMaxFlow(n, s, t, edges):
    // Step 0: 添加反向边 t→s
    edges.add(t, s, 0, INF)
    
    // Step 1: 判断可行流（复用无源汇方法）
    (success, base_flow) = NoSourceSinkFeasibleFlow(n, edges)
    if not success:
        return "无可行流"
    
    // Step 2: 构造残量网络
    residual_graph = 移除所有超级源汇边后的残量网络
    
    // Step 3: 在残量网络上增广
    additional_flow = compute_max_flow(s, t, residual_graph)
    
    // 最终结果
    total_flow = base_flow[t→s] + additional_flow
    return total_flow

有源汇上下界最大流/最小流

这两个其实是一回事，我们对于这个有源汇的上下界网络处理完以后先找到一个可行流，然后在可行流的残量网络的基础上增广出最大流。如果求最大流答案为可行流加最大流，最小流的话答案为可行流减最大流：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Function MaxFlowWithLowerBounds(n, s, t, edges):
    // Step 1: 添加 t→s 的无限容量边
    edges.add(t, s, l=0, r=INF)
    
    // Step 2: 求无源汇可行流
    (is_feasible, base_flow) = FeasibleFlowNoSourceSink(n + 2, edges)
    if not is_feasible:
        return "无可行流"
    
    // Step 3: 构造残量网络（移除超级源汇）
    residual_graph = build_residual_graph(original_graph)
    
    // Step 4: 在残量网络中增广 s→t
    additional_flow = Dinic(residual_graph).max_flow(s, t)
    
    // 最终结果，最小流只要改这里即可
    total_flow = base_flow + additional_flow
    return total_flow