【模板】网络最大流

题目描述

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入输出格式

输入格式

 

第一行包含四个正整数 $n,m,s,t$，分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来M行每行包含三个正整数 $u_i,v_i,w_i$，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，边权为 $w_i$（即该边最大流量为 $w_i$）。

输出格式

 

一行，包含一个正整数，即为该网络的最大流。

输入输出样例

输入样例 #1

4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40

输出样例 #1

50

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
const int N = 1e5 + 10;

int h[N], ne[N], e[N],  idx;
long long flow[N];
int n, m, s, t;
int depth[N];

void add(int a,int b,int c)
{
	e[idx] = b; flow[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
bool bfs()
{
	memset(depth, 0, sizeof depth);
	queue  q;
	q.push(s);
	depth[s] = 1;
	while(q.size())
	{
		int u = q.front();
		q.pop();
		//printf("%d ",u);
		for(int i = h[u]; ~i; i = ne[i])
		{
			int j = e[i];
			if(!flow[i]) continue;
			if(depth[j]) continue;
			q.push(j);
			depth[j] = depth[u] + 1;
		}
	}
	return depth[t];
}

int dfs(int u,long long Flow)
{ 
	if(u == t) return Flow;
	long long res = Flow;
	for(int i = h[u]; ~i ; i = ne[i])
	{
		int j = e[i];
		
		if(flow[i] > 0 && depth[j] == depth[u] + 1)
		{
			long long tmp = dfs(j, min(flow[i], res));
			if(!tmp) depth[j] = 0;
			res -= tmp;
			flow[i] -= tmp;
			flow[i ^ 1] += tmp;
		}
	}
	
	return Flow - res;
}
int main()
{
	scanf("%d %d %d %d", &n, &m, &s, &t);
	memset(h, -1, sizeof h);
	for(int i = 1; i <= m; i++)
	{
		int a, b;
		long long c;
		scanf("%d %d %lld", &a, &b, &c);
		add(a, b, c); add(b, a, 0);
	}
	
	long long ans = 0, tmp;
	while(bfs())
	{
		while(tmp = dfs(s, 1e9))
		{
			ans += tmp;
		}
	}
	
	printf("%lld", ans);
	return 0;
}