ACM-网络流

最大流

FF算法

最基本找増广路的算法

dinic实现(基础的FF算法)

反边：我们知道，当我们在寻找增广路的时候，在前面找出的不一定是最优解，如果我们在减去残量网络中正向边的同时将相对应的反向边加上对应的值，我们就相当于可以反悔从这条边流过。

技巧：flow[u]正边，flow[u^1]反边
建边的时候是同时建的，比如1的反边为2，2的反边为1，▲边不能从0开始

主要思路：

• 求增广路
• 分层图

dinic的优化

• 当前弧优化(作用不明显)

  // 最原始
  int dfs(int now,int fl){
      if(now==aim)return fl;
      int f=e;
          for(int u=fir[now];u && fl;u=nxt[u]){
          if(flow[uj&&deep[to[u]]==deep[now]+1){
              int x=dfs(to[u],min(fl,flow[u]));
              flow[u]-=x;flow[u^1]+=x;fl-=x;f+=x;
          }
      }
      if(lf)deep[now]=-2;
      return f;
  }
  // 当前弧优化
  int dfs(int now,int fl){
      if(now==aim) return fl;
      int f=0;
      // 修改为curfir[now]
      for(int u=curfir[now];u&&fl;u=nxt[u]){
          curfir=u;	// 加了此处
          if(flow[u]&&deep[to[u]]==deep[now]+1){
              int dfs(to[u],min(fl,flow[u]));
              flow[u]-=x;flow[u^1]+=x;fl-=x;f+=x;
          }
      }
      if(!f)deep[now]=-2;	// 炸点优化
      return f;
  }

• 多路增广

• 炸点

最大流最小割定理：最小割总和的权值==最大流的值，对于每张图都是成立的。（网络流的对称形式）

具体代码:

int maxflow(int s, int t){	// 外层循环
	aim = T;int ret = 0;
	while(bfs(s, t)){
		ret += dfs(s, 1<<30);
	}
	return ret;
}

bool bfs(int s, int t){		// 建立分层图
	memset(deep,0,(tot+2)<<2);
    deep[S]=1;d1[1]=S;int head=0,tail=1;
    while(head!=tail){
    	int v=dl[++head];
        for(int u=fir[v];u;u=nxt[u]){
            if(flow[u]&&!deep[to[u]]){
            deep[to[u]]=deep[v]+1;
            d1[++tail]=to[u];
            }
        }
    }
    return deep[T];
}

int dfs(int now,int fl){	// dfs找増广路
    if(now==aim) return fl;
    int f=0;
    // // 当前弧优化,修改为curfir[now]
    for(int u=curfir[now];u&&fl;u=nxt[u]){
        curfir=u;	// 加了此处
        if(flow[u]&&deep[to[u]]==deep[now]+1){
            int dfs(to[u],min(fl,flow[u]));
            flow[u]-=x;flow[u^1]+=x;fl-=x;f+=x;
        }
    }
    if(!f)deep[now]=-2;	// 炸点优化
    return f;
}

EK算法

引入了反相边：在原有的有向图上引入了反向的边，且容量相等

执行过程：
BFS找増广路

• 找到的话，更新最大流、残余网路
• 找不到则走完了

两者的思想都是：找増广路，找到找不到为止

参考:

最大流（最小割）的EK算法

最小费用最大流