Visits: 236

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