网络流初识二（EK算法）

EK算法是解决最大流问题常用的算法之一，复杂度优于FF算法。EK算法的思路和FF算法是一样的。不同之处是EK算法通过广搜寻路，FF算法深搜寻路。

EK算法的具体步骤：

首先是存图，可以采用邻接矩阵直接存，这种存图方式是比较简单的，后面更新残余网络也比较容易，但是空间复杂度比较高，不实用。

另外一种存图方式是链式前向星存图。构造边的时候同时构造两个，正向边和逆向边。加入说正向边的编号为0，那么逆向边的编号为1，依次类推，即偶数为正向边，偶数+1为其对应的负向边。这样存的好处就是，如果我们知道了其中一边，比如说编号为3的这条边，那么它对应的正向边就是3^1=2，如果我们知道了2这条边，那么它对应的反向边就是2^1。

然后是EK算法的核心就是通过BFS寻找一条从原点s到汇点t的一条增广路径。同时用数组dis[]护寻找到当前点的流量。当到达汇点t时，那么这条增广路径的流量dis[t]。

然后更新残留网络，对刚才从s到t所经过的路径的边权进行流量更新，所以这就要求我们应该记录上一步搜索所走过的路径。

最后叠加流量直到找不到增广路径为止。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,s,t;
const ll N=1e5+7;
const ll INF=1e18+7;
struct stu{
    ll to,val,nxt;
}edge[N];
ll tol=0,head[N];
ll flag[200+7][200+7];
void add(ll x,ll y,ll z){
    edge[tol].to=y;
    edge[tol].val=z;
    edge[tol].nxt=head[x];
    head[x]=tol++;
}
ll dis[N];
ll p[N];//记录每个节点的编号。，并不是其父节点。，因为其父节点就是当前节点对应的反向边 的另一个端点。 
ll ans=0;
bool mark[N];
bool EK(ll s,ll t){
    memset(mark,0,sizeof mark);
    queue<ll>que;
    que.push(s);
    mark[s]=1;
    dis[s]=INF;
    while(que.size()){
        ll u=que.front();
        que.pop();
        for(ll i=head[u];i!=-1;i=edge[i].nxt){
            ll v=edge[i].to;
            if(mark[v])continue ;
            if(edge[i].val==0) continue ;
            mark[v]=1;
            p[v]=i;
            que.push(v);
            dis[v]=min(dis[u],edge[i].val); 
            if(v==t) return 1;
        }
    }
    return 0;
}


void update(){
    ll x=t;
    while(x!=s){
        ll v=p[x];
        edge[v].val-=dis[t];
        edge[v^1].val+=dis[t];
        x=edge[v^1].to;
    }
    ans+=dis[t];
}
int main(){
    cin>>n>>m>>s>>t;
    ll x,y,z;
    memset(head,-1,sizeof head); 
    for(ll i=0;i<m;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        if(flag[x][y]==0){//处理重边 
            add(x,y,z);
            flag[x][y]=tol;
            add(y,x,0);
        }
        else edge[flag[x][y]-1].val+=z;
    }
    while(EK(s,t)){
        update();
    }
    printf("%lld
",ans);
    return 0;
}