Edmonds-Karp网络流模板

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define CLR(a) memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;

const int maxn=2010;
const int maxm=20010;


int tot=-1;//因为要利用成对的特性，所以只能从奇数开始，然后++tot作为第一条边  
int ver[maxm],edge[maxm],head[maxm],Next[maxm];
int v[maxn],incf[maxn],pre[maxn];
void addedge(int u,int v,int w){
	ver[++tot]=v,edge[tot]=w,Next[tot]=head[u],head[u]=tot;
	ver[++tot]=u,edge[tot]=0,Next[tot]=head[v],head[v]=tot;
}
int maxflow=0;
int n,m;
int S,T;


bool bfs(){
	memset(v,0,sizeof(v));
	queue<int>q;
	q.push(S);
	v[S]=1;
	incf[S]=INF;
	while(q.size()){
		int x = q.front();q.pop();
		for(int i=head[x];i!=-1;i=Next[i]){
			if(edge[i]){
				int y = ver[i];
				if(v[y])continue;
				incf[y]=min(incf[x],edge[i]);
				pre[y]=i;
				q.push(y),v[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(){
	memset(head,-1,sizeof(head));
	scanf("%d%d", &n,&m);
	S=1,T=n;
	int u,v,w;
	rep(i,1,m){
		scanf("%d%d%d", &u,&v,&w);
		addedge(u,v,w);
	}
	while(bfs())update();
	cout<<maxflow<<endl;
	
	return 0; 
}