# 題目: 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的最大流量

# 解題方法

先建表，按題目要求存為雙向
接著跑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/