题目地址：P4843 清理雪道
上下界网络流
无源汇上下界可行流
给定 \(n\) 个点， \(m\) 条边的网络，求一个可行解，使得边 \((u,v)\) 的流量介于 \([B(u,v),C(u,v)]\) 之间，并且整个网络满足流量守恒。
如果把 \(C-B\) 作为容量上界， \(0\) 作为容量下界，就是一般的网络流模型。
然而求出的实际流量为 \(f(u,v)+B(u,v)\) ，不一定满足流量守恒，需要调整。
设 \(inB[u]=\sum B(i,u)\) ， \(outB[u]=\sum B(u,i)\) ， \(d[u]=inB[u]-outB[u]\) 。
新建源汇， \(S\) 向 \(d>0\) 的点连边， \(d<0\) 的点向 \(T\) 连边，容量为相应的 \(d\) 。
在该网络上求最大流，则每条边的流量 \(+\) 下界就是原网络的一个可行流。
具体实现时，可省略 \(inB,outB\) 数组，直接在 \(d\) 数组上修改。
有源汇上下界可行流
从 \(T\) 到 \(S\) 连一条下界为 \(0\) ，上界为 \(+inf\) 的边，把汇流入的流量转移给源流出的流量，转化为无源汇的网络，然后求解无源汇上下界可行流。
有源汇上下界最小流
两个方法：
- 二分答案 \(ans\) ，从 \(T\) 到 \(S\) 连一条下界为 \(0\) ，上界为 \(ans\) 的边，转化为无源汇网络。找到最小的 \(ans\) ，使得该无源汇上下界网络有可行流。
- 类似有源汇上下界可行流的构图方法，但先不添加 \(T\) 到 \(S\) 的边，求一次超级源到超级汇的最大流。然后再添加一条从 \(T\) 到 \(S\) 下界为 \(0\) ，上界为 \(+inf\) 的边，在残量网络上再求一次超级源到超级汇的最大流。流经 \(T\) 到 \(S\) 的边的流量就是最小流的值。该算法的思想是在第一步中尽可能填充循环流，以减小最小流的代价。
连边：
- \((s,i,0,+inf)\) ；
- \((i,t,0,+inf)\) ；
- 对每条雪道，连边 \((i,j,1,+inf)\) 。
对网络 \(s-t\) 求有源汇上下界最小流。
这里使用方法二。
#include <bits/stdc++.h>
using namespace std;
const int N = 106, M = 2e4 + 6, inf = 1e9;
int n, s, t, S, T, d[N], ans;
int Head[N], Edge[M], Leng[M], Next[M], tot = 1;
inline void add(int x, int y, int z) {
Edge[++tot] = y;
Leng[tot] = z;
Next[tot] = Head[x];
Head[x] = tot;
Edge[++tot] = x;
Leng[tot] = 0;
Next[tot] = Head[y];
Head[y] = tot;
}
inline void ins(int x, int y, int l, int r) {
add(x, y, r - l);
d[x] -= l;
d[y] += l;
}
inline bool bfs() {
memset(d, 0, sizeof(d));
queue<int> q;
q.push(S);
d[S] = 1;
while (q.size()) {
int x = q.front();
q.pop();
for (int i = Head[x]; i; i = Next[i]) {
int y = Edge[i], z = Leng[i];
if (d[y] || !z) continue;
q.push(y);
d[y] = d[x] + 1;
if (y == T) return 1;
}
}
return 0;
}
int dinic(int x, int flow) {
if (x == T) return flow;
int rest = flow;
for (int i = Head[x]; i && rest; i = Next[i]) {
int y = Edge[i], z = Leng[i];
if (d[y] != d[x] + 1 || !z) continue;
int k = dinic(y, min(rest, z));
if (!k) d[y] = 0;
else {
Leng[i] -= k;
Leng[i^1] += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
cin >> n;
s = n + 1, t = n + 2, S = n + 3, T = n + 4;
for (int i = 1; i <= n; i++) {
ins(s, i, 0, inf);
ins(i, t, 0, inf);
int k;
scanf("%d", &k);
while (k--) {
int x;
scanf("%d", &x);
ins(i, x, 1, inf);
}
}
for (int i = 1; i <= t; i++) {
if (d[i] > 0) add(S, i, d[i]);
else if (d[i] < 0) add(i, T, -d[i]);
}
while (bfs()) while (dinic(S, inf));
ins(t, s, 0, inf);
while (bfs()) while (dinic(S, inf));
cout << Leng[tot] << endl;
return 0;
}