【网络流】解题报告：luogu P2740草地排水Drainage Ditches（Edmonds-Karp增广路）

题目链接：草地排水

若一条从源点到汇点的路径上各条边的剩余容量都大于0，则称这条路径为一条增广路。

Edmonds-Karp增广路的策略就是不断用bfs寻找增广路，直至网络中不在存在增广路为止。

在每次寻找增广路的过程中，EK算法只考虑图中所有即剩余容量大于0的边。这样用bfs寻找增广路，并计算路径上各边剩余容量的最小值minf，最后网络的流量就可以增加minf。（想象成水管，最后只能流出所有管道里口径最小的流量。）
但是当一条边的流量时，根据斜对称性质，它的反向边流量，则必有，因此我们还需要考虑每条边的反向边。
因此我们利用成对变换技巧，每条边只记录剩余流量即可，当一条边流过大小为e的流时，令的剩余流量减少e，的剩余流量增加e（想一想，为什么） 的时间复杂度为，但是在实际运用时效率往往很高，一般能处理~ 规模的网络。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<math.h>
#include<cstring>
#include<bitset>
#include<vector>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 2e3+7;
const int M = 5e3+7;

int head[N],nex[M],ver[M],tot = 1,edge[M];
int vis[N],incf[N],pre[N];
int n,m,s,t,maxflow;

void add(int x,int y,int z){//建正边和反边
    ver[++tot] = y;edge[tot] = z;nex[tot] = head[x];head[x] = tot;
    ver[++tot] = x;edge[tot] = 0;nex[tot] = head[y];head[y] = tot;
}

bool bfs(){//bfs找增广路
    memset(vis,0,sizeof vis);
    queue<int>q;
    q.push(s);
    vis[s] = 1;
    incf[s] = INF;//增广路上各边的最小剩余容量
    while(q.size()){
        int x = q.front();
        q.pop();
        for(int i = head[x];i;i = nex[i]){
            if(edge[i]){//只有剩余容量>0才往下走
                int y = ver[i];
                if(vis[y])continue;
                incf[y] = min(incf[x],edge[i]);
                pre[y] = i;//存前驱，用于找到最长路的实际方案
                q.push(y);vis[y] = 1;
                if(y == t)return 1;
            }
        }
    }
    return 0;
}

void update(){//更新增广路及其反向边的剩余容量
    int x = t;
    while(x != s){
        int i = pre[x];
        edge[i] -= incf[t];
        edge[i ^ 1] += incf[t];
        x = ver[i ^ 1];//成对变换
    }
    maxflow += incf[t];
}

int main(){
    while(cin>>m>>n){
        memset(head,0,sizeof head);
        s = 1,t = n;tot = 1;maxflow = 0;
        over(i,1,m){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
        }
        while(bfs())
            update();
        printf("%d\n",maxflow);
    }
    return 0;
}