CF708D Incorrect Flow 题解

CF708D Incorrect Flow

题意

• 给定一张 $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)$。

然后跑有源汇上下界最小费用可行流即可。

代码

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;
}