# 題目: UVa 11418 - Clever Naming Patterns

# 題目說明

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

---

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

---

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

# 解題方法

此題可視為一個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