Network Flow (Miscellaneous Records)

Simply speaking, network flow is an algorithm for judging the maximum flow from S to T in the graph. It's not difficult. Look at it well. Here are a few blogs to recommend: (Code Reference No. 2)
Look at this first: https://blog.csdn.net/mmy1996/article/details/71056041
The most detailed description: https://blog.csdn.net/x_y_q_/article/details/51999466
Advancement: https://blog.csdn.net/giskun/article/details/41492999
Here's a personal story.

network flow

Learning network flow must learn to search. If you can't search, go to my previous blog. Below with the idea of search to consider the problem, in the search graph, the graph is bidirectional, in the network flow, the graph is bidirectional. So there is a reverse side (emphasis), and the rest is the same as BFS. Detailed comments are included in the code.

Reverse side

It is suggested to draw more pictures if the opposite side is technical. In fact, just draw more pictures and come out.

Reference Code

int arr[100][100];/// Store current residual traffic (including reverse side)
int brr[100][100];/// upper limit of storage flow
int p[100];/// Path Point of Current Road
int minn[100];/// Flow value at each point
int wangll(int again,int end) {//Looking and recalling BFS
	queue<int> Q;
	int S = 0;
	while (!Q.empty()) Q.pop();/// Assurance Air Force
	memset(arr, 0, sizeof(arr));
	while (1) {/// Similar to BFS
		memset(minn, 0, sizeof(minn));
		minn[again] = 999;
		Q.push(again);
		while (!Q.empty()) {
			int now = Q.front();
			Q.pop();
			for (int i = 1; i <= m; i++) {
				if (minn[i] == 0 && brr[now][i] > arr[now][i]){
					p[i] = now;/// Marker Backtracking
					Q.push(i);
					minn[i] = min(minn[now], brr[now][i] - arr[now][i]);
				}
			}
		}
		if (arr[end] == 0) break;/// No access, end
		for (int now = end; now != again; now = p[now]) {/// Set up the reverse side (it is recommended to repeatedly deliberate)
			arr[p[now]][now] += minn[end];
			arr[now][p[now]] -= minn[end];
		}
		S += minn[end];/// Calculate the sum of each path
	}
	return S;
}

Complete code

#include<iostream>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
#include<iomanip>
#include<map>
#include<set>
#include<functional>
using namespace std;
int n, m;
int arr[100][100];/// Store current residual traffic (including reverse side)
int brr[100][100];/// upper limit of storage flow
int p[100];/// Path Point of Current Road
int minn[100];/// Flow value at each point
int wangll(int again,int end) {//Looking and recalling BFS
	queue<int> Q;
	int S = 0;
	while (!Q.empty()) Q.pop();/// Assurance Air Force
	memset(arr, 0, sizeof(arr));
	while (1) {/// Similar to BFS
		memset(minn, 0, sizeof(minn));
		minn[again] = 999;
		Q.push(again);
		while (!Q.empty()) {
			int now = Q.front();
			Q.pop();
			for (int i = 1; i <= m; i++) {
				if (minn[i] == 0 && brr[now][i] > arr[now][i]){
					p[i] = now;/// Marker Backtracking
					Q.push(i);
					minn[i] = min(minn[now], brr[now][i] - arr[now][i]);
				}
			}
		}
		if (arr[end] == 0) break;/// No access, end
		for (int now = end; now != again; now = p[now]) {/// Set up the reverse side (it is recommended to repeatedly deliberate)
			arr[p[now]][now] += minn[end];
			arr[now][p[now]] -= minn[end];
		}
		S += minn[end];/// Calculate the sum of each path
	}
	return S;
}

int main()
{
	while (cin >> n >> m) {
		memset(arr, 0, sizeof(arr));
		memset(p, 0, sizeof(p));
		for (int i = 1; i <= n; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			brr[u][v] += w;
		}
		cout << wangll(1, m) << endl;
	}
	return 0;
}

Write at the end

Network flow belongs to paper tiger, just look scary, just look more, or draw more.

Keywords: network REST

Added by jswash on Wed, 31 Jul 2019 04:37:14 +0300