# 題目: UVa 11418 - Clever Naming Patterns

# 題目說明

有 N 組字詞，裡面分別有 N(K) 個字
你需要從每組字詞中取出一個字，必須按照字母排序

例如題目中的:
3
2 Apples Oranges
1 Bananas
5 Apricots Blueberries Cranberries Zuccini Yams

N 為 3 ，所以必須取 3 個字，且開頭須為 A 、 B 、 C
我們取第一組的 Apples
第二組的 Bananas
第三組的 Cranberries
排序後輸出

INPUT:
第一行輸入一個整數 T ，代表測資數
每筆測資第一行輸入一個整數 N ，代表有 N 組字詞
接下來有 N 行，先輸入一個整數 K ，接下來再輸入 K 個字

OUTPUT:
按順序輸出每種不重複字首字母的字

# 解題方法

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

此題可視為一個 S -> teams -> words -> alphabet -> T 的聯通圖
(起點連到字詞組、字詞組連到字、字連到字母、字母連到終點)
找出此圖的 maxflow 即為答案

先建表，建立上述所有的邊
建立一個 vector<string> node ，儲存編號對應的字串
之後跑 Maximum flow 的演算法，(此題利用 Edmonds-Karp)
最後再按照字詞組與字的連接狀況找出答案

# 參考程式碼 (dfs)

	#include <iostream>
	#include <memory.h>
	#include <vector>
	#include <algorithm>
	#include <queue>

	using namespace std;

	// connected graph: S -> teams -> words -> alphabet -> T
	int T, N, K;
	int STW; // size of S + teams + words
	int _T; // size except T
	string str;
	vector<string> node;
	vector<string> ret;
	int G[710][710];
	bool vis[710];

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

	void init()
	{
	memset(G, 0, sizeof(G));
	node.clear();
	ret.clear();
	}

	void build()
	{
	STW = node.size();
	for (char i = 'A'; i <= 'Z'; ++i) node.emplace_back(string(1, i)); // build node(alphabet)

	_T = node.size();
	node.emplace_back("_T"); // build node(T)

	for (int i = STW; i < _T; ++i) G[i][_T] = 1; // connect alphabet to T
	for (int i = N + 1; i < STW; ++i)
	{
	if (node[i][0] - 'A' < N)
	G[i][node[i][0] - 'A' + STW] = 1; // connect words to alphabet
	}
	}

	void read()
	{
	cin >> N;
	node.emplace_back("_S"); // build node(S)
	for (int i = 0; i < N; ++i) node.emplace_back("_N"); // build node(teams)

	for (int i = 1; i <= N; ++i)
	{
	cin >> K;
	for (int j = 0; j < K; ++j)
	{
	cin >> str;
	for (auto& c : str) c = tolower(c);
	str[0] = toupper(str[0]);

	G[i][node.size()] = 1; // connect teams to words
	node.emplace_back(str); // build node(words)
	}

	G[0][i] = 1; // connect S to teams
	}

	build();
	}

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

	for (int i = 0; i < node.size(); ++i) if (G[u][i] > 0 && !vis[i] && dfs(i, v, c))
	{
	--G[u][i];
	++G[i][u];
	return true;
	}

	return false;
	}

	void maxflow()
	{
	while (1)
	{
	memset(vis, false, sizeof(vis));
	if (!dfs(0, node.size() - 1, 1)) break;
	}
	}

	// check if teams to words is connected or not
	void result()
	{
	for (int j = N + 1; j < STW; ++j) for (int i = 1; i <= N; ++i)
	{
	if (!G[i][j] && G[j][i])
	{
	ret.emplace_back(node[j]);
	break;
	}
	}
	sort(ret.begin(), ret.end());
	}

	int main()
	{
	fast_io();

	cin >> T;
	for (int Case = 1; Case <= T; ++Case)
	{
	init();
	read();
	maxflow();
	result();

	cout << "Case #" << Case << ":\n";
	for (auto& s : ret) cout << s << "\n";
	}
	}

# 參考程式碼 (bfs)

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

	using namespace std;

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

	int T, N, K;
	string str;
	int _s = 0, _t;
	int G[710][710];
	int P[710];
	bool vis[710];
	vector<string> ans;
	vector<string> words;

	void init()
	{
	memset(G, 0, sizeof(G));
	memset(P, 0, sizeof(P));
	ans.clear();
	words.clear();
	}

	void read()
	{
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
	G[_s][i] = 1;
	cin >> K;

	for (int j = 0; j < K; ++j)
	{
	cin >> str;
	for (auto& c : str) c = tolower(c);
	str[0] = toupper(str[0]);

	words.emplace_back(str);
	G[i][words.size() + N] = 1;
	}
	}

	_t = words.size() + N + 27;
	for (int i = 1; i <= words.size(); ++i) G[N + i][words.size() + N + (words[i - 1][0] - 'A') + 1] = 1;
	for (int i = 1; i <= 26; ++i) G[words.size() + N + i][_t] = 1;
	}

	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;
	}

	void 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 = _s; v <= _t; ++v) if (!vis[v] && G[u][v] > 0)
	{
	Q.emplace(v);
	P[v] = u;
	vis[v] = true;
	}
	}

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

	for (int j = 1; j <= words.size(); ++j) for (int i = 1; i <= N; ++i)
	{
	if (!G[i][N + j] && G[N + j][i])
	{
	ans.emplace_back(words[j - 1]);
	break;
	}
	}

	sort(ans.begin(), ans.end());
	}

	int main()
	{
	cin >> T;

	for (int Case = 1; Case <= T; ++Case)
	{
	init();
	read();
	maxflow();

	cout << "Case #" << Case << ":\n";
	for (auto& s : ans) cout << s << "\n";
	}
	}

# 參考資料

https://www.larrysprognotes.com/UVa-11418/
https://www.pinghenotes.com/Uva-820-Internet-Bandwidth/
https://instant.1point3acres.com/thread/142145