dinic 最大流模板

/*
 * Author : Echo
 * Email : [e-mail] 
 * Description : dinic 算法模板
 * Created Time : 2017/8/30 10:05:30
 * Last Modify : 2017/9/25 15:55:30
 * File Name : C:\Users\user\Desktop\板子\Dinic.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#define LL long long
#define mem(a,k) memset(a,k,sizeof(a))
using namespace std;
const int maxint = -1u>>1;
const int maxn=210;     //最大点个数
const int maxm=4000;    //最大边条数
struct Edge{
int to;
int value;
int next;
};
struct Graph{
    Edge an[maxm];      //存边
int head[maxn];     //链式前向星的表头
int cnt;            //记录存放了多少条边
int dist[maxn];     //记录bfs的层次
int n,m,src,sink;   //src 源点, sink 汇点
void add(int u,int v,int value){    //加边
        an[++cnt].to=v;
        an[cnt].value=value;
        an[cnt].next=head[u];
        head[u]=cnt;
        an[++cnt].to=u;
        an[cnt].value=0;
        an[cnt].next=head[v];
        head[v]=cnt;
    }
void clear(){       //初始化
memset(head,-1,sizeof(head));
        cnt=1;
    }
int minn(int a,int b){  
return a<b? a:b;
    }

bool bfs(){         //建立层次图
memset(dist,0,sizeof(dist));
        dist[src]=1;
queue<int>que;
        que.push(src);
while(!que.empty()){
int u=que.front();
            que.pop();
for(int i=head[u];i!=-1;i=an[i].next){
if(an[i].value&&dist[an[i].to]==0){
                    dist[an[i].to]=dist[u]+1;
                    que.push(an[i].to);
                }
            }
        }
return dist[sink]>0;
    }
int dfs(int u,int delta){//寻找层次图上的增广路
if(u==sink) return delta;
int res=0,used=0;
for(int i=head[u];delta&&i!=-1;i=an[i].next){
if(an[i].value && dist[u]+1==dist[an[i].to]){
int ff=dfs(an[i].to,minn(delta,an[i].value));
                an[i].value-=ff;
                an[i^1].value+=ff;
                res+=ff;
                delta-=ff;
                used+=ff;
            }
        }
if(used==0) dist[u]=-1;        //一个非常重要的优化
return res;
    }
int dinic(){  
int res=0;
while(bfs()){
int f;
while((f=dfs(src,maxint))) res += f;
        }
return res;
    }
}g;
int main(){
int t;
cin>>t;
while(t--){
        g.clear();
scanf("%d%d",&g.n,&g.m);
scanf("%d%d",&g.src,&g.sink);
for(int i=1;i<=g.m;i++){
int u,v,s;
scanf("%d%d%d",&u,&v,&s);
            g.add(u,v,s*10000+1);
        }
printf("%d\n",g.dinic()%10000);       
    }
return 0;
}


/*

2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 3

 */