# 題目: UVa 11380 - Down Went The Titanic

# 題目說明

給一個 X * Y 的圖，求 * (人) 能走到 # (終點) 的最大數量

* 碎冰上站著一個人 (起點)， capacity 為 1
. 碎冰， capacity 為 1
@ 厚冰， capacity 為無限
~ 海， capacity 為 0
# 木頭 (終點)， capacity 為 P

INPUT:
輸入三個整數 X 、 Y 、 P
接著輸入 X * Y 個 char

OUTPUT:
輸出 * (人) 能走到 # (終點) 的最大數量

# 解題方法

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

點上的 capacity 可視為兩個相連的點，連線的 capacity 為點上的 capacity
再根據 上下左右 中可以走的點做連接
最後跑 Ford Fulkerson 演算法，得出 maximum flow

例如第一個側資
3 4 2
~~#
...@
.~.

S 為 0 、 T 為 25
1 ~ 12 分別為圖上的點
13 ~ 24 為分離出來的點
所以會由 S(0) -> 圖上的點(1 ~ 12) -> 分離出來的點(13 ~ 24) -> 上下左右圖上的點 -> ...... -> T(25)

# 參考程式碼

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

	using namespace std;

	int X, Y, P;
	int _s = 0, _t;
	char c;
	int G[2000][2000];
	int p[2000];
	bool vis[2000];
	int m[4][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };

	void fast_io()
	{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	}

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

	void read_build()
	{
	int node = X * Y;
	_t = node * 2 + 1;

	for (int j = 0; j < Y; ++j) for (int i = 0; i < X; ++i)
	{
	int u = X * j + i + 1;
	cin >> c;

	if (c == '.') G[u][u + node] = 1;
	else if (c == '@') G[u][u + node] = INT_MAX;
	else if (c == '*')
	{
	G[u][u + node] = 1;
	G[_s][u] = 1;
	}
	else if (c == '#')
	{
	G[u][u + node] = INT_MAX;
	G[u + node][_t] = P;
	}

	for (int k = 0; k < 4; ++k)
	{
	int x = i + m[k][0];
	int y = j + m[k][1];

	if (x >= 0 && y >= 0 && x < X && y < Y)
	{
	int v = X * y + x + 1;
	G[u + node][v] = INT_MAX;
	}
	}
	}
	}

	int findflow(int u, int v, int c)
	{
	if (v == _s) return c;
	c = findflow(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 i = 0; i <= _t; ++i) if (!vis[i] && G[u][i] > 0)
	{
	Q.emplace(i);
	vis[i] = true;
	p[i] = u;
	}
	}

	if (!vis[_t]) break;
	ret += findflow(p[_t], _t, INT_MAX);
	}

	return ret;
	}

	int main()
	{
	fast_io();

	while (cin >> Y >> X >> P)
	{
	init();
	read_build();
	cout << maxflow() << "\n";
	}
	}

# 參考資料

https://www.larrysprognotes.com/UVa-11380/

C++ UVa Maximum flow Ford Fulkerson Edmonds-Karp