[BOJ 18767 // C++] 조교 배치

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18767번 문제인 조교 배치이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/18767 

18767번: 조교 배치

source와 각 조교지원자를 capacity 1, 조교지원자와 각자가 희망하는 실험실을 capacity 1, 각 실험실과 sink를 각 실험실마다 배정할 수 있는 인원만큼의 capacity인 간선을 넣고 최대 유량을 흘려보자.

 

이 때의 최대 유량은 뽑을 수 있는 최대 인원 수를 의미하고, 각 조교지원자에서 실험실방향으로 흐른 유량은 그 실험실에 조교가 배정되었다는 의미로 해석할 수 있다.

 

아래는 제출한 소스코드이다.

#define NODE 10005
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int source, sink;
short edge[NODE][NODE];
vector<int> G[NODE];
int level[NODE];

bool dinic_bfs() { // 현 단계의 level graph 생성; 리턴값: 성공여부
	memset(level, 0, sizeof(level));
	level[source] = 1;
	queue<int> que;
	que.push(source);
	while (!que.empty()) {
		int& cur = que.front();
		for (auto& node : G[cur]) {
			if (edge[cur][node] && level[node] == 0) {
				level[node] = level[cur] + 1;
				que.push(node);
			}
		}
		que.pop();
	}

	return level[sink];
}

int turn[NODE];

short dinic_dfs(int cur, short flow) { // flow값 오버플로우 주의
	if (cur == sink) return flow;
	int cursize = G[cur].size();
	for (int& i = turn[cur]; i < cursize; i++) {
		int& node = G[cur][i];
		if (edge[cur][node] && level[node] == level[cur] + 1) {
			int tmp = dinic_dfs(node, min(edge[cur][node], flow));
			if (tmp) {
				edge[cur][node] -= tmp;
				edge[node][cur] += tmp;
				return tmp;
			}
		}
	}

	return 0;
}

int dinic() { // 실제 maximum flow 계산
	int ret = 0;
	while (dinic_bfs()) {
		memset(turn, 0, sizeof(turn));
		int f;
		while (f = dinic_dfs(source, 11111)) ret += f;
	}

	return ret;
}

void solve() {
	for (auto& v : G) v.clear();
	source = 0, sink = 10004;
	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		edge[source][i] = edge[i][source] = 0;
		edge[10001][i] = edge[i][10001] = 0;
		edge[10002][i] = edge[i][10002] = 0;
		edge[10003][i] = edge[i][10003] = 0;
	}
	edge[10001][sink] = edge[10002][sink] = edge[10003][sink] = edge[sink][10001] = edge[sink][10002] = edge[sink][10003] = 0;

	for (int i = 1; i <= N; i++) {
		edge[source][i] = 1;
		G[source].emplace_back(i);
		G[i].emplace_back(source);
	}
	for (int i = 10001; i < 10004; i++) {
		int x; cin >> x;
		edge[i][sink] = x;
		G[i].emplace_back(sink);
		G[sink].emplace_back(i);
	}
	for (int i = 10001; i < 10004; i++) {
		int K; cin >> K;
		while (K--) {
			int x; cin >> x;
			edge[x][i] = 1;
			G[i].emplace_back(x);
			G[x].emplace_back(i);
		}
	}
	cout << dinic() << '\n';
	for (int i = 1; i <= N; i++) {
		if (edge[10001][i]) cout << i << ' ' << 'A' << '\n';
		else if (edge[10002][i]) cout << i << ' ' << 'B' << '\n';
		else if (edge[10003][i]) cout << i << ' ' << 'C' << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) solve();
}