网络流应用（一）

无源汇上下界可行流

题目：

给定一个包含 n 个点 m 条边的有向图，每条边都有一个流量下界和流量上界。

求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

code

#include
using namespace std;
const int N = 210, M = (10200 + N) * 2;
const int INF = 1e8;
int n, m, S, T;
int A[N];

int e[M], f[M], l[M], ne[M], h[M], idx;
void add(int u, int v, int c, int d){
    e[idx] = v, f[idx] = d - c, l[idx] = c, ne[idx] = h[u], h[u] = idx++;
    e[idx] = u, f[idx] = 0, ne[idx] = h[v], h[v] = idx++;
}

int q[N], cur[N], d[N];
bool bfs(){
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, cur[S] = h[S], d[S] = 0;
    while(hh <= tt){
        int u = q[hh++];
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            if(d[v] == -1 && f[i]){
                d[v] = d[u] + 1;
                cur[v] = h[v];
                if(v == T) return true;
                q[++tt] = v;
            }
        }
    }
    return false;
}

int find(int u, int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
        cur[u] = i;
        int v = e[i];
        if(d[v] == d[u] + 1 && f[i]){
            int t = find(v, min(f[i], limit - flow));
            if(!t) d[v] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic(){
    int res = 0, flow;
    while(bfs()) while(flow = find(S, INF)) res += flow;
    return res;
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    S = 0, T = n + 1;
    for(int i = 1; i <= m; i++){
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d); // a 到 b 之间有边，下界为c，上界为d
        add(a, b, c, d);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for(int i = 1; i <= n; i++){
        if(A[i] > 0) add(S, i, 0, A[i]), tot += A[i];
        else if(A[i] < 0) add(i, T, 0, -A[i]);
    }
    if(tot == dinic()){
        puts("YES");
        for(int i = 0; i < 2 * m; i += 2){
            if(e[i] >= 1 && e[i] <= n){
                printf("%d\n", f[i ^ 1] + l[i]);
            }
        }
    }
    else puts("NO");
    return 0;
}

有源汇上下界最大流

题目：

给定一个包含 nn 个点 mm 条边的有向图，每条边都有一个流量下界和流量上界。

给定源点 SS 和汇点 TT，求源点到汇点的最大流。

code

【s、t：题目给出的源点和汇点， S、T：虚拟源点和汇点】
const int N = 220, M = (1e4 + N + 20) * 2;
const int INF = 1e8;
int n, m, s, t, S, T;
int A[N];

int e[M], f[M], ne[M], h[M], idx;
void add(int u, int v, int c){
    e[idx] = v, f[idx] = c, ne[idx] = h[u], h[u] = idx++;
    e[idx] = u, f[idx] = 0, ne[idx] = h[v], h[v] = idx++;
}

int q[N], cur[N], d[N];
bool bfs(){
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, cur[S] = h[S], d[S] = 0;
    while(hh <= tt){
        int u = q[hh++];
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            if(d[v] == -1 && f[i]){
                d[v] = d[u] + 1;
                cur[v] = h[v];
                if(v == T) return true;
                q[++tt] = v;
            }
        }
    }
    return false;
}

int find(int u, int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
        cur[u] = i;
        int v = e[i];
        if(d[v] == d[u] + 1 && f[i]){
            int t = find(v, min(f[i], limit - flow));
            if(!t) d[v] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic(){
    int res = 0, flow;
    while(bfs()) while(flow = find(S, INF)) res += flow;
    return res;
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d%d%d", &n, &m, &s, &t);
    S = 0, T = n + 1;
    for(int i = 1; i <= m; i++){
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, d - c);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for(int i = 1; i <= n; i++){
        if(A[i] > 0) add(S, i, A[i]), tot += A[i];
        else if(A[i] < 0) add(i, T, -A[i]);
    }
    add(t, s, INF);
    if(tot == dinic()){
        S = s, T = t;
        int res = f[idx - 1];
        f[idx - 1] = 0, f[idx - 2] = 0;
        printf("%d\n", res + dinic());
    }
    else puts("No Solution");
    return 0;
}

有源汇上下界最小流

题目：

给定一个包含 nn 个点 mm 条边的有向图，每条边都有一个流量下界和流量上界。

给定源点 SS 和汇点 TT，求源点到汇点的最小流。

注意，为了方便，本题做出如下约定：

• 可行流流量 = 从源点流出的流量 - 流入源点的流量，可以为负值。
• 例如，当 S→TS→T 的流量为 00，T→ST→S 的流量为 1010 时，S→TS→T 的流量为 −10−10。

code

const int N = 50010, M = (125003  + N + 20) * 2;
const int INF = 1e8;
int n, m, s, t, S, T;
int A[N];

int e[M], f[M], ne[M], h[M], idx;
void add(int u, int v, int c){
    e[idx] = v, f[idx] = c, ne[idx] = h[u], h[u] = idx++;
    e[idx] = u, f[idx] = 0, ne[idx] = h[v], h[v] = idx++;
}

int q[N], cur[N], d[N];
bool bfs(){
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, cur[S] = h[S], d[S] = 0;
    while(hh <= tt){
        int u = q[hh++];
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            if(d[v] == -1 && f[i]){
                d[v] = d[u] + 1;
                cur[v] = h[v];
                if(v == T) return true;
                q[++tt] = v;
            }
        }
    }
    return false;
}

int find(int u, int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
        cur[u] = i;
        int v = e[i];
        if(d[v] == d[u] + 1 && f[i]){
            int t = find(v, min(f[i], limit - flow));
            if(!t) d[v] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic(){
    int res = 0, flow;
    while(bfs()) while(flow = find(S, INF)) res += flow;
    return res;
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d%d%d", &n, &m, &s, &t);
    S = 0, T = n + 1;
    for(int i = 1; i <= m; i++){
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, d - c);
        A[a] -= c, A[b] += c;
    }
    int tot = 0;
    for(int i = 1; i <= n; i++){
        if(A[i] > 0) add(S, i, A[i]), tot += A[i];
        else if(A[i] < 0) add(i, T, -A[i]);
    }
    add(t, s, INF);
    if(tot == dinic()){
        S = t, T = s;
        int res = f[idx - 1];
        f[idx - 1] = 0, f[idx - 2] = 0;
        printf("%d\n", res - dinic());
    }
    else puts("No Solution");
    return 0;
}

多源汇最大流

建S、T，从S到每个s连一条INF的边，每个t到T连一条INF的边（代码就不放了，套模板）