D21 网络流 最大流 Dinic 算法

/*
网络流最大流（Dinic 算法）：有向图中较快得到最大流
注：无向图可以转化为有向图，所以可以说dinic同时适合有向图和无向图。

数据结构：
1、带对称边（反向边）的边目录。
注意：
（1）、不能使用a[++alen]代替 ++alen;a[alen]，会出错。
（2）、建立有向边和无向边的区别在于反向边的权值是否为0.
（3）、无论是建立一条有向边还是一条无向边，一次建边函数的调用都是建2条边（原始边和它的反向边）
void ins(int x,int y,int c)//建无向边
{
    ++alen;a[alen]=edge{x,y,c,last[x],alen+1};last[x]=alen;
    ++alen;a[alen]=edge{y,x,c,last[y],alen-1};last[y]=alen;
}
void ins(int x,int y,int c)//建有向边
{
    ++alen;a[alen]=edge{x,y,c,last[x],alen+1};last[x]=alen;
    ++alen;a[alen]=edge{y,x,0,last[y],alen-1};last[y]=alen;
}
2、层次图，h[]数组：h[i]表示点i是第几层的点，即点i到出发点最少经过的边。
出发点为第0层，与出发点直接相连的点为第1层，依次类推。

算法过程：
（1）、bool bfs()函数：建立层次图（就是赋值h[]数组）。
初始化h数组为0，从st出发，只走权值>0的边，用宽搜赋值h[]数组，
最后return h[ed]>0(如果h[ed]==0，则没有人能走到结束点);
（2）、int dinic(int x,int f)：找最大流函数（递归），表示当前在点x有f个人准备去目标点。
如果h[ed]>0，则准备无穷多人从st出发，每个人只走层次比当前点多1的点，
最后如果有t个人到了ed，那么这t个人路过的边的权值都要减t（相应的反向边要加t）；
（3）、一直重复（1）和（2）。
当然，算法是用递归进行的，递归的特点是代码简洁，但细节控制很难。特别是此算法的效率非常依赖2个剪枝。

反向边的存在是为了避免“走自己的路让别人无路可走”。
比如：
4 5
1 2 10
2 4 10
2 3 10
3 4 10
1 3 10
有反向边，答案为20；没反向边，则答案有可能是10（具体看数据给出的顺序）。
如果没有反向边就会是这样：
第一次构建层次图后，有10个人走1-2-3-4，导致第二次构建层次图不成功。
实际上，如果第一次10个人走1-2-4，那么第二次的10个人可以走1-3-4。
就是因为第一次的10个人到了2后，放着2-4这条路不走，偏要走2-3-4。
有了反向边，第二次的10个人到了3后，可以走3-2-4。

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110,M=11100;
struct node{int x,y;LL f; int pre;}a[M];int alen,last[N];
void ins(int x,int y,LL f)
{
    alen++;a[alen]=node{x,y,f,last[x]};last[x]=alen;
    alen++;a[alen]=node{y,x,0,last[y]};last[y]=alen;
}

int h[N],st,ed,n,m;
bool bfs()
{
	deque<int>q;q.clear();
    memset(h,0,sizeof(h));h[st]=1;
    q.push_back(st);
    while(!q.empty())
    {
        int x=q.front();q.pop_front();
        for(int k=last[x];k>0;k=a[k].pre)if(a[k].f)
        {
            int y=a[k].y;
            if(h[y]==0)
            {
                h[y]=h[x]+1;
                q.push_back(y);
            }
        }
    }
    return h[ed]>0;
}

LL dinic(int x,LL f)
{
    if(x==ed)return f;
    LL sx=0;
    for(int k=last[x];k;k=a[k].pre)if(a[k].f)
    {
        int y=a[k].y;
        if(h[y]==h[x]+1)
        {
            LL sy=dinic(y,min(a[k].f,f-sx));
            a[k].f-=sy;a[k^1].f+=sy;
            sx+=sy;if(sx==f)return f;
        }
    }
    if(sx==0)h[x]=0;
    return sx;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    alen=1;memset(last,0,sizeof(last));
    for(int i=1;i<=m;i++)
	{
        int x,y;LL f;scanf("%d%d%lld",&x,&y,&f);
        ins(x,y,f);
    }
    //dinic过程：如果存在层次图就探索存在的流
    LL s=0;
    while( bfs() )
    {
        s+=dinic(st,(LL)1<<62);
    }
    printf("%lld",s);
    return 0;
}