Maxflow, but with an undirected graph.

<aside> 🔑 The problem gives multiple same edges with the same/different weights, just sum them up and run the maxflow algorithm.

</aside>

Table of contents

Problem statement:

On the Internet, machines (nodes) are richly interconnected, and many paths may exist between a given pair of nodes. The total message-carrying capacity (bandwidth) between two given nodes is the maximal amount of data per unit time that can be transmitted from one node to the other. Using a technique called packet switching, this data can be transmitted along several paths at the same time. For example, the following figure shows a network with four nodes (shown as circles), with a total of five connections among them. Every connection is labeled with a bandwidth that represents its data-carrying capacity per unit time. In our example, the bandwidth between node 1 and node 4 is 25, which might be thought of as the sum of the bandwidths 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4. No other combination of paths between nodes 1 and 4 provides a larger bandwidth. You must write a program that computes the bandwidth between two given nodes in a network, given the individual bandwidths of all the connections in the network. In this problem, assume that the bandwidth of a connection is always the same in both directions (which is not necessarily true in the real world).

A Brief Introduction to the problem:

給一張無向圖，找出起始點到終點的最大流。

Input / Output:

給一整數代表有幾個節點，節點編號為$1-n$。接下來分別有$S,T,C$三個整數，分別代表原點與終點和編的數量，接下來$C$行每行都為一條邊，輸入格式為$V1,V2,W$，代表$V1$與$V2$互連且權重為$W$，當代表$Node$個數的變數為$0$時程式停止。

輸出格式，Network $[number(start from 1)]$，換行，The bandwidth is $[bandwidth]$.。

Solution:

Mindset:

最大流，只不過是無向圖，建圖方法為將無向邊視為兩條方向相反的有向邊，且剩餘容量相等。建好圖之後跑最大流演算法即可求解。

<aside> ⚠️ 題目會給相同的邊，例如2-3和3-2因為是無向所以為同邊，但兩次輸入給的權重要累加在一起計算，跑出來的才是正確答案。

</aside>

Pictures for Example:

測資1的圖，和題目提供的基本一樣，只是把邊改成有向邊，雙向容量相同。

Code example [Accepted]:

#include <iostream>
#include <unordered_map>
#include <string>
#include <utility>
#include <limits.h>
#include <queue>
#include <vector>
#include <cmath>
#include <stack>
#include <sstream>
#define IO_Optimization cin.tie(0);ios_base::sync_with_stdio(0);cout.tie(0)
#define endline '\\n'
#define ll long long
#define lenn size()

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
// 840 - Internet Bandwidth
const int INFINITE = INT_MAX; int maxflow = 0; bool reach = 0;
int source, sink;
#define dest first
#define weight second
#define qtop q.front()

struct Vertex {
	int lv = 0; bool vis = 0;
	unordered_map < int , int >out;
	Vertex(){}
	Vertex(int level, bool visited) {
		lv = level; vis = visited;
	}
	void AddEdge(int to, int w) { out[to] = w; }
	void AccumulateEdge(int to, int w) { out[to] += w; }
};

unordered_map< int, Vertex >Rsnet; // Residual Network
stack< pair< int, int > >pths; // Record paths

void init() { for (auto& it : Rsnet) { it.second.lv = 0; it.second.vis = 0; } }
void create_layered() { // Construct layered network
	init(); Rsnet[sink].lv = INFINITE;
	queue<int>q; int level = 0; Rsnet[source].lv = level; Rsnet[source].vis = 1;
	q.emplace(source); int t = q.lenn; int tt = 0; level++;
	while (!q.empty()) {
		while (t--) {
			for (auto& v : Rsnet[qtop].out) {
				if (!Rsnet[v.dest].vis && v.weight > 0) {
					q.emplace(v.dest);
					Rsnet[v.dest].vis = 1;
					Rsnet[v.dest].lv = level;
					tt++;
				}
			} q.pop();
		} t = tt; tt = 0; level++;
	}
}
void blockflow(int curr, int minimum) {
	if (curr == sink) {
		reach = 1; maxflow += minimum;
		while (!pths.empty()) {
			auto tmp = pths.top(); Rsnet[tmp.first].out[tmp.second] -= minimum;
			Rsnet[tmp.second].out[tmp.first] += minimum; pths.pop();
		}
		return;
	}
	for (auto& v : Rsnet[curr].out) {
		if (Rsnet[v.dest].lv == Rsnet[curr].lv + 1 && v.weight > 0) {
			pths.emplace(make_pair(curr, v.dest));
			/*send*/ blockflow(v.dest, min(minimum, v.weight));
			if (reach) return;
			pths.pop();
		}
	} return;
}
void Dinic() {
	maxflow = 0;
	while (true) {
		create_layered();
		if (Rsnet[sink].lv == INFINITE) break;
		while (true) {
			reach = false;
			blockflow(source, INFINITE);
			if (!reach) break;
		}
	}
}

int main()
{
	IO_Optimization;
	int n; int tc = 1;
	while (cin >> n && n != 0) {
		Rsnet.clear();
		int s, t, c;
		cin >> s >> t >> c;
		source = s; sink = t;
		for (int i = 0; i < c; i++) {
			int v1, v2, w;
			cin >> v1 >> v2 >> w;
			Rsnet[v1].AccumulateEdge(v2, w);
			Rsnet[v2].AccumulateEdge(v1, w);
		}
		Dinic();
		cout << "Network " << tc++ << endline;
		cout << "The bandwidth is " << maxflow << "." << endline;
		cout << endline;
	}
}