Maximum flow problem

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

                                                                                            ---2021.8.27

1. Network flow :

In a directed graph

u,v Representative vertex G(u,v) For from u To v On the traffic

S Represents the source point ,T Representative meeting point

Maximum flow :

1. The maximum traffic on the source to sink path

2. How to find :

1. utilize dfs() Search the maximum flow from the source point to the sink point , But the maximum flow must be the minimum flow on the path . Then subtract the corresponding minimum flow from the positive side , The opposite side plus the corresponding minimum flow , This is how to build an augmentation path

2. And then use it bfs(） To determine whether there is an augmented path from the source point to the sink point , No end , Find the maximum flow

Template title :

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

AC Code :

#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; }
}
// Based on the current hierarchical graph , Find all the Zengguang roads 
int dfs(int x, int mx)// The current vertex sum and the maximum flow on this augmented path 
{
	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]))))// use dfs Go search   Until we find the minimum traffic on this Zengguang road 
		{
			// Update the residual network 
			g[x][i]-=a;
			g[i][x] += a;// Reverse side building 
			return a;
		}
		
	}
	return 0;
}
void solve()
{
	while (bfs())// Until we can't find a Zengguang road to the destination 
	{
		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;
}