多源汇最大流问题

解题思路

多源汇最大流问题区别于单源汇最大流问题，它存在多个源点，多个汇点。

这里有一个非常明显的建图方式，就是创造一个虚拟源点和一个虚拟汇点。虚拟源点向所有源点连一条容量为 $+\infty$ 的边，所有汇点向虚拟汇点连一条容量为 $+\infty$ 的边。从虚拟源点到虚拟汇点的最大流就是原图的最大流。

为什么这样是正确的呢，只需要证明原图的任意一个可行流都可以变成新图的一个可行流，新图的任意一个可行流都可以变成原图的一个可行流。证明它们之间存在一一对应的关系，那么这样建图就是正确的。

首先，对于原图的任意一个可行流，中间所有的边都不用变，那么中间的所有点都满足容量限制和流量守恒，需要看的是所有源点和汇点是否满足。

可以发现，每一条从虚拟源点到源点的边的流量都是该源点流出的流量之和，保证所有源点都满足容量限制和流量守恒。同理所有汇点也满足容量限制和流量守恒。

因此原图的任意一个可行流都能对应新图的一个可行流。

对于新图的任意一个可行流，中间的边不变，删去所有与虚拟源点、虚拟汇点相关的边，可以发现中间的所有点仍然是满足容量限制和流量守恒的。

因此新图的任意一个可行流都能对应原图的一个可行流。

综上所述，原图的可行流和新图的可行流是一一对应的，所以原图的最大流就是新图的最大流。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = (N + 100000) * 2, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //从u往汇点尽可能多的传输流量，上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        int j = e[i];

        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }

    return flow - rest;
}

int dinic() //用dinic算法求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    int sc, tc; //记录源点和汇点的数量
    scanf("%d%d%d%d", &n, &m, &sc, &tc);

    memset(h, -1, sizeof h); //初始化邻接表

    //建立残量网络
    S = 0, T = n + 1; //虚拟源点、虚拟汇点
    while(sc--)
    {
        int x;
        scanf("%d", &x);
        add(S, x, INF);
    }
    while(tc--)
    {
        int x;
        scanf("%d", &x);
        add(x, T, INF);
    }
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

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

    return 0;
}