「笔记」网络最大流

写在前面

简单记录下板子= =
如果之后有空会来完善（gugugu

基础概念

网络是一张有向图 \(G = (V,E)\)，每条边 \((u,v)\) 都有一个权值 \(c\)，被称为边容量。其中有两个关键点，被称为源点 \(S\) 和汇点 \(T\)。

一张图的流函数 \(f(u,v)\) 被定义为满足下述三个条件的实数函数：

• \(f(u,v)\le c(u,v)\)。
• \(f(u,v) = -f(v,u)\)。
• \(\sum_{(S,x)\in E} f(S,x) = \sum_{(x,T)\in E} f(x, T)\)。

其中 \((u,v)\) 表示一条边，在满足上述三个条件的情况下，流函数可以是任意实数。

对于一条边，\(f(u,v)\) 被称为边的流量，\(c(u,v) - f(u,v)\) 称为边的剩余容量，整个网络的流量为 \(\sum_{(S,x)\in E} f(S,x)\)，即源点的流出量。

可以将流的概念形象地理解为通过许多中继节点的两台电脑之间的数据传输，边可以看做传输线路。每条传输线路的传输量限制是边的容量（对应条件 1），总传输量等于源点的流出量，也等于汇点的接收量（对应条件 2）。

最大流问题即求得从源点到汇点的最大流量 \(f_{max}\)。

FF

对原图中的有向边添加反向边，反向边初始容量为 0。

对于一张图的流函数，其残量网络被定义为网络中所有节点及剩余容量大于 0 的边构成的子图。每一个当前流对应着一个残量网络。
定义一条从源点到汇点的路径上所有边的 剩余容量都大于 0 的路径为增广路。残量网络中一条从源点到汇点的路径一定是增广路。

FF 算法每次从源点开始 dfs 找增广路，找到一条增广路后，令增广路上所有边容量减去增加的流量，并使它们的反边容量加上增加的流量。之后遍历到反边可以认为是流量的“反悔”。

残量网络不存在增广路的充要条件是当前流已是最大流，因此找不到任何增广路后即得最大流。每轮 dfs 可行流流量至少增加 1，总时间复杂度为 \(O(mf_{max})\)。

太菜了不配拥有代码。

EK

Edmonds-Karp

从源点开始 bfs 实现 FF，到达汇点后停止 bfs 并增广一次。增广时记录转移前驱并更新路径上边的残余容量，答案加上最小流量。

时间复杂度 \(O(n m^2)\) 级别。

//知识点：网络最大流，EK
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 210 + 10;
const int kM = 1e4 + 10;
const LL kInf = 9e18 + 2077;
//=============================================================
int n, m, s, t;
int e_num = 1, head[kN], v[kM], ne[kM], from[kN];
LL f[kN], w[kM];
bool vis[kN];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_, int w_) {
  v[++ e_num] = v_;
  w[e_num] = 1ll * w_;
  ne[e_num] = head[u_];
  head[u_] = e_num;
}
bool Bfs() { //找到一条增广路
  memset(vis, false, sizeof (vis));
  std::queue  q; 
  vis[s] = false;
  f[s] = kInf;
  q.push(s);
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i]; 
      LL w_ = w[i];
      if (!w_ || vis[v_]) continue;
      f[v_] = std::min(f[u_], w_);
      vis[v_] = true; 
      from[v_] = i;
      q.push(v_);
      if (v_ == t) return true; 
    }
  }
  return false;
}
LL EK() {
  LL ret = 0;
  while (Bfs()) { //更改路径的残余容量
    for (int u_ = t; u_ != s; u_ = v[from[u_] ^ 1]) {
      w[from[u_]] -= f[t]; 
      w[from[u_] ^ 1] += f[t];
    }
    ret += f[t];
  }
  return ret; 
}
//=============================================================
int main() {
  n = read(), m = read(), s = read(), t = read();
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read(), w_ = read();
    AddEdge(u_, v_, w_);
    AddEdge(v_, u_, 0);
  }
  printf("%lld\n", EK());
  return 0;
}

Dinic

使用 dfs 找增广路，不过在每轮增广前使用 bfs 将残余网络分层。一个点的层数为残余网络上它与源点的最小边数。分层时若汇点的层数不存在，说明不存在增广路，即可停止增广。
之后 dfs 增广时，每次转移仅向比当前点层数多 1 的点转移。这可以保证每次找到的增广路是最短的。

Dinic 有两个优化：多路增广——在残余流量不为 0 时一次 dfs 找多条增广路；当前弧优化——一条边只增广一次。应用多路增广和当前弧优化后，Dinic 的时间复杂度上界是 \(O(n^2m)\)。

//知识点：网络最大流，Dinic
/*
By:Luckyblock
*/
#include 
#include 
#include 
#include 
#include 
#define LL long long
const int kN = 210 + 10;
const int kM = 1e4 + 10;
const LL kInf = 9e18 + 2077;
//=============================================================
int n, m, s, t;
int e_num = 1, head[kN], v[kM], ne[kM];
int cur[kN], dep[kN];
LL w[kM];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void Chkmax(int &fir_, int sec_) {
  if (sec_ > fir_) fir_ = sec_;
}
void Chkmin(int &fir_, int sec_) {
  if (sec_ < fir_) fir_ = sec_;
}
void AddEdge(int u_, int v_, int w_) {
  v[++ e_num] = v_;
  w[e_num] = 1ll * w_;
  ne[e_num] = head[u_];
  head[u_] = e_num;
}
bool Bfs() {
  std::queue  q;
  memset(dep, 0, sizeof (dep));
  dep[s] = 1; //注意初始化 
  q.push(s); 
  while (!q.empty()) {
    int u_ = q.front(); q.pop();
    for (int i = head[u_]; i; i = ne[i]) {
      int v_ = v[i];
      LL w_ = w[i];
      if (w_ > 0 && !dep[v_]) { 
        dep[v_] = dep[u_] + 1;
        q.push(v_);
      }
    }
  }
  return dep[t];
}
LL Dfs(int u_, LL into_) {
  if (u_ == t || !into_) return into_;
  LL out = 0;
  for (int& i = cur[u_]; i && into_; i = ne[i]) { //当前弧优化 
    int v_ = v[i];
    LL w_ = w[i];
    if (dep[v_] == dep[u_] + 1 && w_ > 0) {
      LL ret = Dfs(v_, std::min(into_, w_));
      if (!ret) dep[v_] = kN; //没有贡献，之后不会再访问 
      w[i] -= ret, w[i ^ 1] += ret;
      out += ret, into_ -= ret;
    }
  }
  return out;
}
LL Dinic() {
  LL ret = 0;
  while (Bfs()) {
    for (int i = 1; i <= n; ++ i) cur[i] = head[i]; //初始化当前弧 
    ret += Dfs(s, kInf);
  }
  return ret;
}
//=============================================================
int main() {
  n = read(), m = read(), s = read(), t = read();
  for (int i = 1; i <= m; ++ i) {
    int u_ = read(), v_ = read(), w_ = read();
    AddEdge(u_, v_, w_);
    AddEdge(v_, u_, 0);
  }
  printf("%lld\n", Dinic());
  return 0;
}