最大流学习笔记

由于本人太弱,可能讲解有误,请读者指出。

什么是网络流

网络流是通过构建从源点到汇点的有向图模型来解决图论问题。从理论上讲,网络流可以处理所有二分图问题。
二分图和网络流的难度都在于问题建模,一般不会特意去卡算法效率,所以只需要背一两个简单算法的模板就能应付大部分题目了。

最大流问题

什么是最大流

例题

P3376 【模板】网络最大流

解释例题

将一些物品从结点 \(s\) 运输到结点 \(t\),其中可以通过其他的结点中转,每条边都有一条运输物品上限,求最多有多少物品可以从结点 \(s\) 运输到结点 \(t\)

概念

源点:即结点 \(s\),出发点。
汇点:即结点 \(t\),结束点。
容量:记 \(c(u,v)\),从结点 \(u\) 到结点 \(v\) 的边的运输物品数量上限,若结点 \(u\) 与结点 \(v\) 之间不存在边,\(c(u,v)=0\)
流量:记 \(f(u,v)\),从结点 \(u\) 到结点 \(v\) 的边实际运输物品数量。
残量:每条边的容量与流量之差。
由于若将物品从结点 \(u\) 运输到结点 \(v\),再又将物品运回来是没有任何意义的,所以可以规定 \(f(u,v)=-f(v,u)\)
如图:每个边上第一个数是流量,第二个数是容量

性质

通过这些概念,我们就可以从中挖掘出一些性质:

  • 容量限制:\(f(u,v)\le c(u,v)\)
  • 斜对称性:\(f(u,v)=-f(v,u)\)
  • 流量平衡:\(\sum\limits_{u\ne\{s,t\},(u,v)\in E}f(u,v)=0\)

这是最大流的重要性质,同时也是它的条件。

增广路算法

增广路算法思想很简单:从零流开始不断的增加流量,每一次增加要保持三条性质就行了。
我们通过每一条边的残量建边,对对原有边建立反向边,得到一个残量网络,注意这里边的数量可能达到原图的两倍:


这样,我们只需要基于这样的事实:残量网络中的任何一条 \(s\)\(t\) 的有向道路都对应着一条原图中的增广路。只需要求出该道路中的所有残量最小值 \(d\),把所对应的所有边上的流量增加 \(d\) 即可,这个过程就叫增广。如图,红色的就是一条增广路。

不难验证在增广之后它还是满足三条性质的。
如果当图中不存在增广路时,就说明当前流就是最大流了。
这就是增广路定理。

实现——Edmonds-Karp 算法

对于查找路径,我们可以选用 DFS 或 BFS,但是如果用 DFS 则一不小心就会超时,所以应该选用 BFS来实现,时间复杂度 \(O(nm^2)\)

Code

int Bfs() {
    memset(pre, -1, sizeof(pre));
    for(int i = 1 ; i <= n ; ++ i) flow[i] = INF;
    queue <int> q;
    pre[S] = 0, q.push(S);
    while(!q.empty()) {
        int op = q.front(); q.pop();
        for(int i = 1 ; i <= n ; ++ i) {
            if(i==S||pre[i]!=-1||c[op][i]==0) continue;
            pre[i] = op; //找到未遍历过的点
            flow[i] = min(flow[op], c[op][i]); // 更新路径上的最小值 
            q.push(i);
        }
    }
    if(flow[T]==INF)return -1;
    return flow[T];
}
int Solve() {
    int ans = 0;
    while(true) {
        int k = Bfs();
        if(k==-1) break;
        ans += k;
        int nw = T;
        while(nw!=S) {//更新残余网络 
            c[pre[nw]][nw] -= k;
            c[nw][pre[nw]] += k;
            nw = pre[nw];
        }
    }
    return ans;
}

Dinic 算法

Edmonds-Karp 算法的劣势就在于,每次遍历了一遍残量网络之后只能求出一条增广路来增广。
于是我们针对这一点进行优化,我们就得到了一个更加优秀的替代品,Dinic 算法。
Dinic 算法的关键就是分层图阻塞流

分层图

分层图就是按照结点 \(s\) 到另一个点的最短距离进行分层,相同距离分到一层,就像 \(s\to 第一层\to 第二层\to 第三层\cdots\)。这样就可以得到每一条这样的路径都是 \(s-t\) 最短路。

阻塞流

阻塞流就是指不考虑反向边的“极大流”。每一次增广路后将路径上最小的流量增广,但是减小,再将那条边阻塞。



这就是三次增广后的结果,当图中不存在 \(s-t\) 路径,是增广结束,这就是阻塞流。

时间复杂度

由于最多进行 \(n-1\) 次阻塞流,每次计算不超过 \(O(nm)\),看上去是总时间复杂度是 \(O(n^2m)\),但如果是对于二分图最大匹配这样的图,时间复杂度只有 \(O(n^{\frac{1}{2}}m)\)

Code

struct edge
{
    int to, value, net;
} e[N << 1]; //共有n*2条边
void add(int from, int to, int value)
{ //链式前向星
    cnt++;
    e[cnt].to = to;
    e[cnt].value = value;
    e[cnt].net = head[from];
    head[from] = cnt;
}
int bfs(int st, int ed){ //建立层次图
    queue<int> que;
    memset(dis, -1, sizeof(dis));
    dis[st] = 0;
    que.push(st);
    while (!que.empty()){
        int x = que.front();
        que.pop();
        for (int i = head[x]; i > -1; i = e[i].net){
            int now = e[i].to;
            if (dis[now] == -1 && e[i].value){
                que.push(now);
                dis[now] = dis[x] + 1;
            }
        }
    }
    return dis[ed] != -1;
}
int dfs(int x, int t, int maxflow){
    if (x == t)
        return maxflow;
    int ans = 0;
    for (int i = cur[x]; i > -1; i = e[i].net){ ///当前弧优化
        int now = e[i].to;
        if (dis[now] != dis[x] + 1 || e[i].value == 0 || ans >= maxflow)
            continue;
        cur[x] = i;
        int f = dfs(now, t, min(e[i].value, maxflow - ans));
        e[i].value -= f;
        e[i ^ 1].value += f; //反向边加流量
        ans += f;
    }
    if(!ans)dis[x] = -1;
    return ans;
}
int Dinic(int st, int ed){
    int ans = 0;
    while (bfs(st, ed)){
        memcpy(cur, head, sizeof(head));
        int k;
        while ((k = dfs(st, ed, INF)))
            ans += k;
    }
    return ans;
}

热门相关:峡谷正能量   异世修真邪君   本法官萌萌哒   本法官萌萌哒   买妻种田:山野夫君,强势宠!