# 題目: Uva 820 - Internet Bandwidth

# 題目說明

求 S 到 T 的最大流量

INPUT:
每筆測資第一行輸入一個整數 N ，代表 node 的數量
第二行輸入三個整數 S 、 T 、 C
接下來有 C 行，每行有三個整數 u 、 v 、 w ，代表 u 連到 v ， capacity 為 w
當 N 為 0 時結束程式

OUTPUT:
輸出 S 到 T 的最大流量

# 解題方法

此題的解題概念為 Maximum flow 、 Ford Fulkerson

先建表，按題目要求存為雙向
接著跑 Ford Fulkerson ，每次用 dfs 找到一條 S 到 T 的路徑
並記錄其中最小的 capacity ，直到無法找到一條 S 到 T 的路徑為止
將這些 capacity 相加即為答案

# 參考程式碼 (dfs)

	#include <iostream>
	#include <memory.h>

	using namespace std;

	int N, S, T, C;
	int u, v, w;
	int cases = 0;
	int G[101][101];
	bool vis[101];

	int dfs(int u, int v, int w)
	{
	vis[u] = true;
	if (u == v) return w;

	for (int i = 1; i <= N; ++i) if (G[u][i] > 0 && !vis[i])
	{
	int tmp = dfs(i, v, min(w, G[u][i]));
	if (tmp > 0)
	{
	G[u][i] -= tmp;
	G[i][u] += tmp;
	return tmp;
	}
	}

	return 0;
	}

	int maxflow()
	{
	int ret = 0, tmp;

	while (1)
	{
	memset(vis, false, sizeof(vis));
	int tmp = dfs(S, T, 10001);

	if (tmp <= 0) break;
	else ret += tmp;
	}

	return ret;
	}

	int main()
	{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	while (cin >> N, N)
	{
	// init
	cin >> S >> T >> C;
	memset(G, 0, sizeof(G));

	// store network data
	for (int i = 0; i < C; ++i)
	{
	cin >> u >> v >> w;
	G[u][v] += w;
	G[v][u] += w;
	}

	// find maxflow
	cout << "Network " << ++cases << "\nThe bandwidth is " << maxflow() << ".\n\n";
	}
	}

# 參考程式碼 (bfs)

	#include <iostream>
	#include <queue>
	#include <climits>
	#include <memory.h>

	using namespace std;

	static auto fast_io = []
	{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	return 0;
	}();

	int N, S, T, C;
	int cases = 0;
	int G[105][105];
	int P[105];
	bool vis[105];

	void init()
	{
	memset(G, 0, sizeof(G));
	memset(P, 0, sizeof(P));
	}

	void read()
	{
	int u, v, c;
	cin >> S >> T >> C;

	for (int i = 0; i < C; ++i)
	{
	cin >> u >> v >> c;
	G[u][v] += c;
	G[v][u] += c;
	}
	}

	int updateflow(int u, int v, int c)
	{
	if (v == S) return c;
	c = updateflow(P[u], u, min(G[u][v], c));
	G[u][v] -= c;
	G[v][u] += c;
	return c;
	}

	int maxflow()
	{
	int ret = 0;

	while (1)
	{
	memset(vis, false, sizeof(vis));
	queue<int> Q;
	Q.emplace(S);
	vis[S] = true;

	while (!Q.empty() && !vis[T])
	{
	int u = Q.front();
	Q.pop();

	for (int v = 1; v <= N; ++v) if (!vis[v] && G[u][v] > 0)
	{
	Q.emplace(v);
	vis[v] = true;
	P[v] = u;
	}
	}

	if (!vis[T]) break;
	ret += updateflow(P[T], T, INT_MAX);
	}

	return ret;
	}

	int main()
	{
	while (cin >> N, N)
	{
	init();
	read();
	cout << "Network " << ++cases << "\nThe bandwidth is " << maxflow() << ".\n\n";
	}
	}

# 參考資料

https://henrybear327.github.io/codingBlog/2017/01/17/UVA820/