题解 CF708D 【Incorrect Flow】
xht
2020-03-09 20:54:12
> [CF708D Incorrect Flow](https://codeforces.com/contest/708/problem/D)
## 题意
- 给定一张 $n$ 个点 $m$ 条边的网络，源点为 $1$，汇点为 $n$。
- 对于每条边 $(u,v)$，有容量 $c$，当前流量 $f$。
- 但这个图是错误的，可能存在 $c < f$，或者流量不守恒的情况。
- 你每次操作可以将某条边的 $c$ 或 $f$ 加 $1$ 或减 $1$。
- 请你用最少的操作次数将图变成一个正确的网络。
- $n,m \le 100$，$c,f \le 10^6$，$1$ 没有入边，$n$ 没有出边。
## 题解
建立新的网络，下面用 $(x,y,z,w)$ 表示一条 $x \to y$，容量为 $z$，费用为 $w$ 的边。
首先考虑处理每一条原图中的边，设 $f^\prime$ 表示操作后的流量。
对于 $c \ge f$ 的边：
1. $0 \le f^\prime \le f$：连边 $(v, u, f, 1)$，表示流量每减一，花费加一，最多减 $f$ 次。
2. $f < f^\prime \le c$：连边 $(u, v, c - f, 1)$，表示流量每加一，花费加一，最多加 $c - f$ 次。
3. $f^\prime > c$：连边 $(u, v, +\infty, 2)$，表示流量每加一，花费加二，可以无限加。
对于 $c < f$ 的边，由于至少会产生 $f - c$ 的花费，所以先加上：
1. $0 \le f^\prime < c$：连边 $(v, u, c, 1)$，表示将 $f-c$ 的花费用在将流量减 $f-c$ 上，因此流量每减一，花费加一，最多减 $c$ 次。
2. $c \le f^\prime \le f$：连边 $(v, u, f - c, 0)$，表示将 $f-c$ 的花费用在将流量减 $f - f^\prime$，容量加 $f^\prime - c$ 上，因此流量每减一，花费不变，最多减 $f-c$ 次。
3. $f^\prime > f$：连边 $(u,v,+\infty, 2)$，表示将 $f-c$ 的花费用在将容量加 $f - c$ 上，因此流量每加一，花费加二，可以无限加。
那原本的流量 $f$ 怎么办呢？
考虑把网络改为上下界网络，则对于原图中的一条边，连边 $(u,v,(f,f), 0)$。
然后跑**有源汇上下界最小费用可行流**即可。
## 代码
```cpp
namespace EK {
const int N = 1e4 + 7, M = 1e5 + 7;
const ll inf = 1e18;
int n, S, T, h[N], e[M], t[M], tot, pre[N], v[N];
ll mxf, ans, f[M], c[M], d[N], now[N];
inline void add(int x, int y, ll z, ll w, int o = 1) {
e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
if (o) add(y, x, 0, -w, 0);
}
inline bool spfa() {
for (int i = 1; i <= n; i++) v[i] = 0, d[i] = inf;
queue<int> q;
q.push(S), v[S] = 1, d[S] = 0, now[S] = inf;
while (q.size()) {
int x = q.front();
q.pop(), v[x] = 0;
for (int i = h[x]; i; i = t[i]) {
int y = e[i];
ll z = f[i], w = c[i];
if (!z || d[y] <= d[x] + w) continue;
d[y] = d[x] + w, now[y] = min(now[x], z), pre[y] = i;
if (!v[y]) q.push(y), v[y] = 1;
}
}
return d[T] != inf;
}
inline void upd() {
mxf += now[T], ans += d[T] * now[T];
int x = T;
while (x != S)
f[pre[x]] -= now[T], f[pre[x]^1] += now[T], x = e[pre[x]^1];
}
inline void main() {
while (spfa()) upd();
}
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T, tot = 1, mxf = ans = 0;
for (int i = 1; i <= n; i++) h[i] = 0;
}
}
namespace no_min_cost_flow {
const int N = 1e5 + 7;
int n, S, T;
ll d[N], s;
inline void add(int x, int y, ll l, ll r, ll w) {
EK::add(x, y, r - l, w), d[y] += l, d[x] -= l;
}
inline bool main() {
for (int i = 1; i <= n; i++)
if (d[i] > 0) EK::add(S, i, d[i], 0), s += d[i];
else if (d[i] < 0) EK::add(i, T, -d[i], 0);
EK::main();
return EK::mxf == s;
}
inline void init(int _n) {
n = _n, s = 0, S = n + 1, T = n + 2;
EK::init(n + 2, S, T);
for (int i = 1; i <= n; i++) d[i] = 0;
}
}
const ll inf = 1e18;
ll ans;
int main() {
int n, m, S, T;
rd(n), rd(m), S = 1, T = n;
no_min_cost_flow::init(n);
no_min_cost_flow::add(T, S, 0, inf, 0);
for (int i = 1, u, v, c, f; i <= m; i++) {
rd(u), rd(v), rd(c), rd(f);
no_min_cost_flow::add(u, v, f, f, 0);
if (c >= f) {
no_min_cost_flow::add(v, u, 0, f, 1);
no_min_cost_flow::add(u, v, 0, c - f, 1);
no_min_cost_flow::add(u, v, 0, inf, 2);
} else {
ans += f - c;
no_min_cost_flow::add(v, u, 0, c, 1);
no_min_cost_flow::add(v, u, 0, f - c, 0);
no_min_cost_flow::add(u, v, 0, inf, 2);
}
}
no_min_cost_flow::main();
print(EK::ans + ans);
return 0;
}
```