# 題目: UVa 12873 - The Programmers

# 題目說明

有 P 隊隊伍， S 個組別，每個組別最多能有 C 個隊伍
求參加隊伍的最大數量

INPUT:
第一行輸入一個整數 T ，代表測資數
每筆測資第一行輸入四個整數 P 、 S 、 C 、 m
接下來有 m 行，每行有兩個整數 u 、 v ，代表 u 隊的組別為 v

OUTPUT:
輸出參加隊伍的最大數量

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

此題可視為一個 S -> teams -> sites -> T 的聯通圖
(起點連到隊伍、隊伍連到組別、組別連到終點)
找出此圖的 maxflow 即為答案

先建表，建立上述所有的邊
之後跑 Maximum flow 的演算法，(此題利用 Edmonds-Karp)

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

	using namespace std;

	// connected graph: S -> teams -> sites -> T
	int T, P, S, C, m;
	int _s = 0, _t;
	int u, v;
	int G[530][530];
	bool vis[530];

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

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

	void read()
	{
	cin >> P >> S >> C >> m;

	_t = P + S + 1;

	for (int i = 0; i < m; ++i)
	{
	cin >> u >> v;
	G[u][v + P] = 1; // connect teams to sites
	}
	for (int i = 1; i <= P; ++i) G[_s][i] = 1; // connect S to teams
	for (int i = P + 1; i < _t; ++i) G[i][_t] = C; // connect sites to T
	}

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

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

	return false;
	}

	int maxflow()
	{
	int ret = 0;

	while (1)
	{
	memset(vis, false, sizeof(vis));
	if (dfs(_s, _t)) ++ret;
	else break;
	}

	return ret;
	}

	int main()
	{
	fast_io();

	cin >> T;
	while (T--)
	{
	init();
	read();
	cout << maxflow() << "\n";
	}
	}

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

	using namespace std;

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

	int T, P, S, C, M, u, v;
	int _s = 0, _t;
	int G[550][550];
	int p[550];
	bool vis[550];

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

	void read()
	{
	cin >> P >> S >> C >> M;

	_t = P + S + 1;
	while (M--)
	{
	cin >> u >> v;
	G[u][P + v] = 1;
	}
	for (int i = 1; i <= P; ++i) G[_s][i] = 1;
	for (int i = P + 1; i <= P + S; ++i) G[i][_t] = 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 = _s; v <= _t; ++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()
	{
	cin >> T;

	while (T--)
	{
	init();
	read();
	cout << maxflow() << "\n";
	}
	}