$网络流算法$ 、 $最大流模版$

$$\huge 多源汇最大流$$

问题描述

给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量，边的容量非负。

其中有 Sc 个源点，Tc 个汇点。

求整个网络的最大流。

建图

建立超级源点S,超级汇点T

从S向所有源点连权值为inf的边

从所有汇点向T连权值为inf的边

S到T的最大流 = 整个网络的最大流

证明

对应关系

把S到T的所有可行流删去S和T,就对应了原图的一个可行流

原图的一个可行流

$从S到源点u连一条流量为 \sum_{(u,v)}f(u,v) - \sum_{(v,u)}f(v,u)$
$从汇点u到T连一条流量为 \sum_{(v,u)}f(v,u) - \sum_{(u,v)}f(u,v)$

依然保持流量限制和流量守恒,即新图的一个可行流

故原图的任何一个可行流 与 新图的一个可行流 一一对应

数量关系

$原图的一个可行流流量为\sum_{u \in sc} \left( \sum_{(u,v)}f(u,v) - \sum_{(v,u)}f(v,u) \right) $

$对应到新图中依然是这个流量$

$即原图的最大流 = 新图的最大流$

$证毕$

$Code$

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = (100010 + N) * 2, inf = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], c[M], ne[M], idx;
int q[N], dep[N], cur[N];

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

bool bfs()
{
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dep[j] == -1 && c[i])
            {
                dep[j] = dep[t] + 1;
                cur[j] = h[j];
                if (j == T)return true;
                q[++ tt] = j;
            }
        }
    }
    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 j = e[i];
        if (dep[j] == dep[u] + 1 && c[i])
        {
            int t = find(j, min(c[i], limit - flow));
            if (!t)dep[j] = -1;
            c[i] -= t, c[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()
{
    int sc, tc;
    scanf("%d%d%d%d", &n, &m, &sc, &tc);
    S = 0, T = n + 1;
    memset(h, -1, sizeof h);
    for (int i = 0; i < sc; i ++ )
    {
        int s;
        scanf("%d", &s);
        add(S, s, inf);
    }
    for (int i = 0; i < tc; i ++ )
    {
        int t;
        scanf("%d", &t);
        add(t, T, inf);
    }

    while (m -- )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }

    printf("%d\n", dinic());

    return 0;
}