最大流问题

"For me,my only dream is to help my family lead a better life"

                                                                                            ---2021.8.27

1.网络流:

在一个有向图中

u,v代表顶点 G(u,v)代表从u到v上的流量

S代表源点，T代表汇点

最大流:

1.源点到汇点路径上的最大流量

2.如何求:

1.利用dfs()去搜源点到汇点的最大流，但这个最大流必须是这条路径上的最小流量.然后正向边减去相应的最小流量，反向边加上相应的最小流量，这就是建立增广路径

2.然后利用bfs(）去判断是否能存在源点到汇点的增广路，不存在结束,求出最大流

模板题目:

http://poj.org/problem?id=1273

AC代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x7fffffff
using namespace std;
const int N = 205;
int g[N][N];
int n, m, deep[N], s, t;
int u, v, flow;
int maxflow;
queue<int> q;
bool bfs()
{
	while (!q.empty())q.pop();
	memset(deep, -1, sizeof(deep));
	deep[s] = 0;
	q.push(s);
	while (!q.empty())
	{
		int x = q.front();
		q.pop();
		for (int i = 1; i <= m; ++i)
		{
			if (g[x][i] > 0 && deep[i]== -1)
			{
				deep[i] = deep[x] + 1;
				q.push(i);
			}
		}
	}
	if (deep[t]>0) { return true; }
	else { return false; }
}
//基于当前分层图，找到所有的增广路
int dfs(int x, int mx)//当前顶点和以及这条增广路上的最大流
{
	int a;
	if (x == t) { return mx; }
	for (int i = 1; i <= m; ++i)
	{
		if (g[x][i] > 0 && deep[i] == deep[x] + 1 && (a = dfs(i, min(mx, g[x][i]))))//用dfs去搜 直到找到这条增广路上的最小的流量
		{
			//更新残余网络
			g[x][i]-=a;
			g[i][x] += a;//反向建边
			return a;
		}
		
	}
	return 0;
}
void solve()
{
	while (bfs())//直到找不到一条通往目的地的增广路即结束
	{
		maxflow += dfs(s, INF);
	}
}
int main()
{
	while (scanf("%d %d", &n, &m)!=EOF)
	{
		maxflow = 0;
		s = 1, t = m;
		memset(g, 0, sizeof(g));
		
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d %d %d", &u, &v, &flow);
			g[u][v] += flow;
		}
		solve();
		printf("%d\n", maxflow);
	}
	return 0;
}