lance.h

lance

0%

最大流及dinic算法

发表于 更新于 分类于

最大流及dinic算法

Ford-Fulkerson 增广路算法

通过寻找增广路来更新最大流，有EK，Dinic，SAP，ISAP等算法。

残量网络

对流函数$f$，残量网络$G_f$(Residual Network) 是网络G中所有结点和剩余容量大于0的边构成的子图。
注意：残量网络中包含反向边。

增广路

在原图$G$中，若有一条从源点到汇点的路径的所有边的剩余容量都大于0，则此路为增广路。即残量网络中从源点到汇点的路。

反向边

增广不一定最优，反向边给后续反悔的机会。初始建正边和反边，反边流量为0，在增广时，给反向边加流量。

实现细节

前向星中要记得用成对存（^1 ）

EK动能算法

BFS找增广路，增广之。

  • 找：即BFS找一条路，注意合法性即可
  • 增广：从来的路走一遍，将路上的流量减去，答案加上路上的最小流量。

复杂度$O(nm^2)$(n为点，m为边)

dinic

每次增广前，用BFS将图分层，设源点层数为0，层数即为离源点的距离。
这样的优点是：

  • 如果不存在增广路，可以立即停止（即汇点的层数不存在）
  • 保证每次增广最短的路。

然后DFS找增广路：
每次都只找比当前点层数多1的点增广，这样就不会绕一圈到一个点上比如不会从第6层到第1层。这里要利用DFS将所有路增广掉。

其复杂度为$O(n^2m)$, 实际使用中可以处理1e4-5的网络，在二分图匹配中，复杂度为$O(m \sqrt n)$

优化

  • 多路增广：一次DFS中，增广完还有剩余流量，继续dfs找
  • 当前弧：已经增广过的边不会有第二次。

dinic实现

其中当前弧优化部分，每次BFS都刷新一次，每次dfs中不管用没用完都标记，如果有容量可以走也只能等下一轮bfs了。
那些真正没有流量的，一种是自己没流量了，这个在bfs中判断即可。
另一种是后继路径没有流量了，这个在dfs中剪枝，让这个点的deg为0，这只是对这个dfs有效，在下一轮中没有影响。

以下是算法竞赛进阶指南中的带有优化的dinic模版，使用链式前向星存图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

const ll INF=0x7fffffffffffffffll;
const int N=1e5+10,M=2e5+10;
ll n,m,s,t,T,x,y,v,c;
ll head[N],ver[M<<1],edge[M<<1],nxt[M<<1],d[N],now[M<<1];
ll tot,maxflow;
queue<int> q;
void add(int x,int y,int c){
  ver[++tot]=y;edge[tot]=c;nxt[tot]=head[x];head[x]=tot;
  ver[++tot]=x;edge[tot]=0;nxt[tot]=head[y];head[y]=tot;
}

bool bfs(){
  memset(d,0,sizeof d);
  while(q.size())q.pop();
  q.push(s);now[s]=head[s];d[s]=1;
  while(q.size()){
    int x=q.front();q.pop();
    for(int i=head[x];i;i=nxt[i]){
      if(edge[i]&&!d[ver[i]]){
        q.push(ver[i]);
        now[ver[i]]=head[ver[i]];
        d[ver[i]]=d[x]+1;
        if(ver[i]==t)return 1;
      }
    }
  }
  return 0;
}
ll dinic(ll x,ll flow){//传一个允许最大流(源点当然是无穷)
  if(x==t)return flow;
  ll rest=flow,k,i;
  for(i=now[x];i&&rest;i=nxt[i]){
    if(edge[i]&&d[ver[i]]==d[x]+1){
      k=dinic(ver[i],min(rest,edge[i]));
      if(!k)d[ver[i]]=0;
      edge[i]-=k;
      edge[i^1]+=k;
      rest-=k;
    }
  }
  now[x]=i;
  return flow-rest;
}

int main()
{
  maxflow=0;
  cin>>n>>m>>s>>t;
  tot=1;//0buneng
  for(int i=1;i<=m;++i){
    scanf("%d%d%d",&x,&y,&c);
    add(x,y,c);
  }
  ll flow=0;
  while(bfs())
    while(flow=dinic(s,INF))maxflow+=flow;
  cout<<maxflow<<endl;
  return 0;
}