网络

图论中的网络是一种特殊的有向图，与有向图不同的是网络存在容量、源点和汇点

  • $E$ 边集中的每一条边 $(u,v)$ 都有一个被称为容量的权值 $c$
  • $V$ 点集中存在两个特殊点：源点 $s$ 和汇点 $t$

在网络 $G=(V,E)$ 中，流是一个从边集到整数集的一个函数，$f(u,v)$ 表示边 $(u,v)$ 上的流量，$c(u,v)-f(u,v)$ 表示这条边的剩余容量

在网络中，合法的可行的流应该满足性质：

  • 容量限制：$0\le f(u,v)\le c(u,v)$
  • 流量守恒：$\sum\limits_{(u,x)\in E} f(u,x)=\sum\limits_{(x,v)\in E} f(x,v),x\ne \{s,t\} $ ，形象化的说，一个普通点流入的容量等于流出的容量

最大流问题

我们希望在网络 $G=(V,E)$ 中找到合适的流 $f$ ，最大化这个网络的流量 $\lvert f\rvert =\sum\limits_{x\in V}f(s,x)-\sum\limits_{x\in V}f(x,s)$

增广路： 一条从源点到汇点的路径，路径上所有边的剩余容量都大于 $0$

残留网： 网络中所有结点和剩余容量大于 $0$ 的所有边构成的子图

EK算法

在建图时给每个有向边都构建一条反向边，容量为 $0$ ，目的是提供一条退流的路径，一旦前方的增广路无法连通可行流，那么就可以通过退流管道将增广路的部分流量退回

因为需要快速的定位反向边，所以采用链式前向星的方式存图

struct edge{int v; LL c; int ne;};
edge e[M];
int h[210], idx = 1;//从2开始给边进行编号，0是哨兵

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

for (int i = 1; i <= m; i++){
    int u, v;
    LL c;
    cin >> u >> v >> c;
    add(u, v, c);
    add(v, u, 0);
}

通过 BFS 找到一条增广路

类似贪心的扩展，每次只走到一个没有被访问过的节点

int pre[210];//记录节点的前驱边
LL mf[210];//s到该点的流量上限

bool bfs(void){
    memset(mf, 0, sizeof mf);
    queue<int> q;
    q.push(s);
    mf[s] = 1e9;
    while (q.size()){
        int u = q.front();
        q.pop();
        for (int i = h[u]; i; i = e[i].ne){//枚举所有出边
            int v = e[i].v;
            if (mf[v] == 0 && e[i].c){//只有这个邻点没有被访问过且有容量
                mf[v] = min(mf[u], e[i].c);
                pre[v] = i;
                q.push(v);
                if (v == t) return 1;//能走到汇点
            }
        }
    }
    return 0;//不能走到汇点，说明无可行流
}

每轮 BFS 都找到一条可行流，累加这些流的流量，然后构建残留网

LL EK(void){
    LL flow = 0;
    while (bfs()){//存在可行流时
        int v=t;//从汇点出发
        while (v != s){//回溯到源点
            int i = pre[v];
            e[i].c -= mf[t];
            e[i^1].c += mf[t];//更新退流管道
            v = e[i^1].v;//走反向边
        }
        flow += mf[t];
    }
    return flow;//返回最大流
}

总的时间复杂度上界为 $O(nm^2)$ 的级别，$n,m$ 分别为点数和边数，实际上会比这快得多

Dinic算法

区别于 EK 算法每一轮只累加一条增广路的流量，我们可以先将点 BFS 分层然后通过 DFS 寻找多条增广路

LL dfs(int u, LL mf){
    if (u == t) return mf;//如果到终点，返回流量
    LL res = 0;
    for (int i = cur[u]; i; i = e[i].ne){
        cur[u] = i;//当前弧优化
        int v = e[i].v;
        if (dep[v] == dep[u] + 1 && e[i].w){//只有当下一个节点是下一层时才搜索
            LL f = dfs(v, min(mf, e[i].w));//流量限制
            e[i].w -= f;
            e[i ^ 1].w += f;//退流
            res += f;//累加当前流量
            mf -= f;
            if (mf == 0) break;//如果当前节点以及没有流量就立即返回
        }
    }
    if (res == 0) dep[u] = 0;//残枝优化
    return res;
}

其中的当前弧 cur[u] 表示节点 $u$ 在链式前向星中已经考虑过了哪些边，再次进入循环时就可以跳过这些边

残枝优化的意义时，如果当前节点的 res 为 $0$ ，这个节点就不会连通到汇点，所以在当前的残留网中就不需要考虑了

LL dinic(){
    LL flow = 0;
    while (bfs()){
        memcpy(cur, h, sizeof h);//重置当前弧
        flow += dfs(s, 1e9);//累加可行流
    }
    return flow;
}

时间复杂度为 $O(n^2m)$ 级别，在稠密图中的运行效率很优