上下界网络流总结

2024-03-28 21:06:52

参考：

[1] : https://blog.csdn.net/corsica6/article/details/81488993

[2] : https://www.luogu.com.cn/problemnew/solution/P4553

说明

可行流：一个网络网络中，存在一条流，满足任意点的总流入量等于总流出量（即流量守恒）。
边的流量：网络流连边时连的反向边上的flowflowflow值，即为该边流量。（考虑在流过这条边时，在正向边上减去了流量大小的值，而反向边上恰好加上了这个值）。

无源汇上下界可行流

给定 \(n\) 个点， \(m\) 条边的网络，求一个可行解，使得边 \((u,v)\) 的流量介于 \([B(u,v),C(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。

在该网络上求最大流，则每条边的流量+下界就是原网络的一个可行流。

有源汇上下界可行流

从T到S连一条下界为0，上届为 +inf 的边，在原网络中，从S到T的流量全部流回去，流量守恒，然后转换成了无源汇的网络，然后求解无源汇上下界可行流即可。

最终T->S 这条边的流量为原图总流量

有源汇上下界最大流

求出可行流之后，再求原残余网络的最大流，之前的可行流再加上残余网络最大流就是原来的最大流

有源汇上下界最小流

求出可行流，然后T->S的边的流量即为可行流大小，再原图残余网络中从T->S 跑最大流，用可行流减去残余网络最大流，就是最小流。

注：原图不包括T->S 的边以及S'和T'所连接的所有边

例题

BZOJ-3698. XWW的难题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
const int N = 250 + 5;
const int M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
int n, m, s, t, s_, t_, tot, maxflow;
double a[N][N];
queue<int> q;
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, nxt[tot] = head[y], head[y] = tot;
}
bool bfs(){
    memset(d, 0, sizeof d);
    while(q.size())q.pop();
    q.push(s);d[s] = 1;
    while(q.size()){
        int x = q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            if(edge[i] && !d[ver[i]]){
                q.push(ver[i]);
                d[ver[i]] = d[x] + 1;
                if(ver[i] == t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x, int flow){
    if(x == t) return flow;
    int rest = flow, k;
    for(int i=head[x];i && rest; i=nxt[i]){
       	if(edge[i] && d[ver[i]] == d[x] + 1){
            k = dinic(ver[i], min(rest, edge[i]));
            if(!k) d[ver[i]] = 0;
            edge[i] -= k;
            edge[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}
void ins(int x, int y, int l, int r){
    add(x, y, r-l);
    d[x] -= l;
    d[y] += l;
}
int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%lf", &a[i][j]);
        }
    }
    tot = 1;
    s_ = 2 * n + 1, t_ = s_ + 1, s = t_ + 1, t = s + 1;
    for(int i=1;i<=n-1;i++){
        ins(s_, i,  trunc(a[i][n]), ceil(a[i][n]));
        ins(i+n, t_, trunc(a[n][i]), ceil(a[n][i]));
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            ins(i, j+n, trunc(a[i][j]),ceil(a[i][j]));
        }
    }
    int sum = 0;
    for(int i=1;i<=t_;i++){
        if(d[i] > 0) {
            sum += d[i];
            add(s, i, d[i]);
        } else if (d[i] < 0){
            add(i, t, -d[i]);
        }
    }
    // dbg(sum);
    add(t_, s_, inf);
    while(bfs()) maxflow += dinic(s, inf);
    // dbg(sum, maxflow);
    if(sum != maxflow) {
        puts("NO");
        return 0;
    }
    maxflow = edge[tot];
    edge[tot] = edge[tot-1] = 0;
    s = s_; t = t_;
    while(bfs()) maxflow += dinic(s, inf);
    cout << maxflow * 3 << endl;
    return 0;
}

P4843 清理雪道

// 有源汇上下界网络流
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
const int N = 100010 + 5;
const int M = 100010;
int head[N], ver[M], nxt[M], edge[M], d[N];
int n, m, s_, t_, s, t, tot, maxflow;
queue<int> q;
void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
    ver[++tot] = x, edge[tot] = 0, nxt[tot] = head[y], head[y] = tot;
}
bool bfs(){
    memset(d, 0, sizeof d);
    while(q.size())q.pop();
    q.push(s);d[s] = 1;
    while(q.size()){
        int x = q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            if(edge[i] && !d[ver[i]]){
                q.push(ver[i]);
                d[ver[i]] = d[x] + 1;
                if(ver[i] == t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x, int flow){
    if(x == t) return flow;
    int rest = flow, k;
    for(int i=head[x];i && rest; i=nxt[i]){
       	if(edge[i] && d[ver[i]] == d[x] + 1){
            k = dinic(ver[i], min(rest, edge[i]));
            if(!k) d[ver[i]] = 0;
            edge[i] -= k;
            edge[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}
void ins(int x, int y, int l, int r){
    add(x, y, inf);
    d[x] -= l;
    d[y] += l;
}   
int main(){
    scanf("%d", &n);
    tot = 1;
    s_ = 0, t_ = n + 1, s = t_ + 1, t = s + 1;
    for(int i=1;i<=n;i++){
        int k,x;scanf("%d", &k);
        while(k--){
            scanf("%d", &x);
            ins(i, x, 1, inf);
        }
        add(s_, i, inf);
        add(i, t_, inf);
    }
    for(int i=1;i<=n;i++){
        if(d[i] < 0) add(i, t, -d[i]);
        else if(d[i] > 0) add(s, i, d[i]);
    }
    add(t_, s_, inf);
    while(bfs()) maxflow += dinic(s, inf);
    int res = edge[tot]; 
    maxflow = 0;
    edge[tot] = edge[tot^1] = 0;
    s = t_, t = s_;
    while(bfs()) maxflow += dinic(s, inf);
    //dbg(res, maxflow);
    printf("%d\n", res - maxflow);
    return 0;
}

P4553 80人环游世界

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }
const int N = 100000 + 5;
const int M = 1000010;
int head[N], nxt[M], ver[M], edge[M], cost[M];
int d[N], incf[N], pre[N], v[N];
int n, m, tot, s, t, s_, S, T, maxflow, ans;
void add(int x, int y, int z, int c){
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot, cost[tot] = c;
    ver[++tot] = x, edge[tot] = 0, nxt[tot] = head[y], head[y] = tot, cost[tot] = -c;
}
inline void ins(int x, int y, int l, int r, int c){
    add(x, y, r - l, c);
    d[x] -= l; d[y] += l;
}
bool spfa(){
    queue<int> q;
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    q.push(S);
    d[S] = 0, v[S] = 1;
    incf[S] = m;
    while(q.size()){
        int x = q.front();q.pop();
        v[x] = 0;
        for(int i=head[x];i;i=nxt[i]){
            if(!edge[i]) continue;
            int y = ver[i];
            if(d[y] > d[x] + cost[i]){
                d[y] = d[x] + cost[i];
                incf[y] = min(incf[x], edge[i]);
                pre[y] = i;
                if(!v[y]) v[y] = 1, q.push(y);
            }
        }
    }
    if(d[T] == inf) return false;
    return true;
}
void update(){
    int x = T;
    while(x != S){
        int i = pre[x];
        edge[i] -= incf[T];
        edge[i^1] += incf[T];
        x = ver[i^1];
    }
    maxflow += incf[T];
    ans += d[T] * incf[T];
}
int main(){
    tot = 1;
    scanf("%d%d", &n, &m);
    s = 2 * n + 1, t = s + 1, s_ = t + 1, S = s_ + 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()) update();
    cout << ans << endl;
    return 0;

}

码农公寓