网络流 | 马克图布

网络流

算法图论

发布日期: 2023-03-19

文章字数: 800

阅读时长: 3 分

阅读次数:

参考：OI Wiki|王树深

名词：最大流，阻塞流

最大流一定是阻塞流，但是阻塞流不一定是最大流

m是边，n是节点，f为最大流的大小

Ford-Fulkerson Algorithm（算法复杂度$O(f\cdot m)$，依赖于最大流的大小）

key concept:residual graph

构造residual graph
寻找简单路径
取路径上residual最小的管道流量$p$作为路径上能通过的最大的流量，然后路径上每个管道都减去这个$p$
算法依次进行，直到找不到从$s$到$t$的简单路径

Edmonds-karp Algorithm（算法复杂度$O(m^2\cdot n)$，不依赖于最大流的大小）

key concept:residual graph

构造residual graph
寻找简单路径
取路径上residual最小的管道流量$p$作为路径上能通过的最大的流量，然后路径上每个管道都减去这个$p$
然后按照给这个路径上的管道都建一条反向的边，其流量为$p$
算法依次进行，直到找不到从$s$到$t$的简单路径

EK代码：

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define maxn 250
#define INF 0x3f3f3f3f

struct Edge {
  int from, to, cap, flow;

  Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct EK {
  int n, m;             // n：点数，m：边数
  vector<Edge> edges;   // edges：所有边的集合
  vector<int> G[maxn];  // G：点 x -> x 的所有边在 edges 中的下标
  int a[maxn], p[maxn];  // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
                         // p：点 x -> BFS 过程中最近接近点 x 的边

  void init(int n) {
    for (int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  int Maxflow(int s, int t) {
    int flow = 0;
    for (;;) {
      memset(a, 0, sizeof(a));
      queue<int> Q;
      Q.push(s);
      a[s] = INF;
      while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (int i = 0; i < G[x].size(); i++) {  // 遍历以 x 作为起点的边
          Edge& e = edges[G[x][i]];
          if (!a[e.to] && e.cap > e.flow) {
            p[e.to] = G[x][i];  // G[x][i] 是最近接近点 e.to 的边
            a[e.to] =
                min(a[x], e.cap - e.flow);  // 最近接近点 e.to 的边赋给它的流
            Q.push(e.to);
          }
        }
        if (a[t]) break;  // 如果汇点接受到了流，就退出 BFS
      }
      if (!a[t])
        break;  // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
      for (int u = t; u != s;
           u = edges[p[u]].from) {  // 通过 u 追寻 BFS 过程中 s -> t 的路径
        edges[p[u]].flow += a[t];      // 增加路径上边的 flow 值
        edges[p[u] ^ 1].flow -= a[t];  // 减小反向路径的 flow 值
      }
      flow += a[t];
    }
    return flow;
  }
};

int main(){
  cout << 3;
    return 0;
}