网络流

最大流

描述

在图中，给出每条边的最大流，求出从一给定源点到汇点的最大流

算法

单纯的贪心法由于搜索顺序会导致结果不同的问题并不能保证求出正确的答案，只需要将原始贪心算法中加入一个“反悔”机制就可以保证求出正确答案

实现中只需要加入反向边，没流过一条边，就将这条边的边权减去流量，并把反向边的边权加上这个流量

实际上就是通过加入反向边实现抵消操作

Ford-Fulkerson

dfs

时间复杂度：$O(FE)$

Edmonds-Karp

bfs优化

时间复杂度：$O(E^2V)$

Dinic

每次找一条路前，先通过一次bfs更新每个点的level，目的是在之后的dfs中优先遍历深度浅的点

加入当前弧优化，避免对一条没有用的便进行多次检查

时间复杂度：$O(EV^2)$

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int MAXV=100,INF=1e9;
struct E{int to,cap,rev;};
vector<E> G[MAXV];
int level[MAXV];
int iter[MAXV];//当前弧，在其之前的边已经没有用了
void addEdge(int u,int v,int c)
{
    G[from].push_back((E){u,c,G[to].size()});
    G[to].push_back((E){v,0,G[from].size()-1});
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int v=0;v<G[u].size();v++)
        {
            E & e=G[u][i];
            if(e.cap>0&&level[e.to]<0)
            {
                level[e.to]=level[u]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t) return f;
    for(int & i=iter[v];i<G[v].size();i++)//当前弧优化
    {
        E & e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to])
        {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0)
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
}
int maxFlow(int s,int t)
{
    int flow=0;
    while(true)
    {
        bfs(s);
        if(level[t]<0) return flow;//若bfs搜不到汇点，返回值即可
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0)
            flow+=f;
    }
}

最小割

最大流=最小割

最大流的变体

多个源点和汇点

增加一个超级源点s和一个超级汇点t，从s向每个源点加入一条容量无穷的边，从每一个汇点向t加入一条容量无穷的边

无向图

加两条边即可

顶点上流量限制

把结点“割开”，所有入边连到一点A上，所有出边连到一点B上，从A向B连一条cap为该结点流量限制的边即可

最大流的应用

二分图匹配