P4553 80人环游世界

题目地址：P4553 80人环游世界

上下界网络流

无源汇上下界可行流

如果把 \(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\) 的边，把汇流入的流量转移给源流出的流量，转化为无源汇的网络，然后求解无源汇上下界可行流。

有源汇上下界最小费用可行流

类似有源汇上下界可行流，求最大流改为求最小费用最大流。

每个国家拆成两个点（入点 \(i\) 和出点 \(i+n\)），建立源 \(s\) 汇 \(t\) 附加源 \(s\_\) 。

连边：

\((s,s\_,m,m,0)\) ；
\((s\_,i,0,m,0)\) ；
\((i+n,t,0,m,0)\) ；
\((i,i+n,V[i],V[i],0)\) ；
若 \(i,j\) 两个国家通航，连边 \((i+n,j,0,m,Cost_{i,j})\) 。

对网络 \(s-t\) 求有源汇上下界最小费用可行流。

#include <bits/stdc++.h>
using namespace std;
const int N = 206, M = 1e5 + 6, inf = 0x3f3f3f3f;
int n, m, S, T, s, s_, t, d[N], now[N], pre[N], ans;
int Head[N], Edge[M], Leng[M], Cost[M], Next[M], tot = 1;
bitset<N> v;

inline void add(int x, int y, int z, int w) {
    Edge[++tot] = y;
    Leng[tot] = z;
    Cost[tot] = w;
    Next[tot] = Head[x];
    Head[x] = tot;
    Edge[++tot] = x;
    Leng[tot] = 0;
    Cost[tot] = -w;
    Next[tot] = Head[y];
    Head[y] = tot;
}

inline void ins(int x, int y, int l, int r, int w) {
    add(x, y, r - l, w);
    d[x] -= l;
    d[y] += l;
}

inline bool spfa() {
    v.reset();
    memset(d, 0x3f, sizeof(d));
    queue<int> q;
    q.push(S);
    v[S] = 1;
    d[S] = 0;
    now[S] = m;
    while (q.size()) {
        int x = q.front();
        q.pop();
        v[x] = 0;
        for (int i = Head[x]; i; i = Next[i]) {
            int y = Edge[i], z = Leng[i], w = Cost[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() {
    ans += d[T] * now[T];
    int x = T;
    while (x != S) {
        int i = pre[x];
        Leng[i] -= now[T];
        Leng[i^1] += now[T];
        x = Edge[i^1];
    }
}

int main() {
    cin >> n >> m;
    s = n * 2 + 1, s_ = s + 1, t = s_ + 1;
    S = t + 1, T = S + 1;
    ins(s, s_, m, m, 0);
    for (int i = 1; i <= n; i++) {
        ins(s_, i, 0, m, 0);
        ins(i + n, t, 0, m, 0);
        int x;
        scanf("%d", &x);
        ins(i, i + n, x, x, 0);
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            int x;
            scanf("%d", &x);
            if (~x) ins(i + n, j, 0, m, x);
        }
//  ins(t, s, 0, m, 0);
    for (int i = 1; i <= t; i++) {
        if (d[i] > 0) add(S, i, d[i], 0);
        else if (d[i] < 0) add(i, T, -d[i], 0);
    }
    while (spfa()) upd();
    cout << ans << endl;
    return 0;
}

注意：代码中注释的那一条语句加不加都可以AC，具体原因有待研究（讨论）