CF708D Incorrect Flow 题解

作者: xht37 分类: 题解 发布时间: 2020-03-09 20:54

点击数:49

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注