boj, 백준) 1733.등번호 ( C / C++)

1. 문제 링크

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

1733번: 등번호

2. 문제 개요

한 선수가 최대 두 가지의 번호를 부여받을 수 있다. 각 선수들이 어떤 번호를 선택해야 모든 선수들의 번호가 중복되지 않을 수 있을지 구하는 문제.

 

3. 문제 힌트

일반적인 O(VE)시간복잡도의 이분 매칭으로는 시간 초과다. 호프 크로프트 카프 알고리즘 O(V^(1/2) E)을 사용하자.

그리고 불가능하다면 불가능한 선수만 -1로 출력하지말고 전체 출력을 -1로 해줘야 한다(맞왜틀..)

 

4. 문제 풀이

N을 입력받고 각 행번째의 선수들이 부여받을 수 있는 번호를 vector에 저장하자.

그리고 알고리즘을 구현해서 실행하면 된다.

호프 크로프트 카프 알고리즘은 alternating path를 찾는 게 핵심이다.

 

5. 코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int INF = 987654321;

int n, match;
vector<vector<int>> adj;
vector<int> xy, yx, label;


void bfs()
{
	queue<int> q;

	for (int i = 1; i <= n; ++i) {
		if (xy[i] == -1) {
			label[i] = 0;
			q.push(i);
		}
		else
			label[i] = INF;
	}

	while (!q.empty()) {
		int cur = q.front(); q.pop();

		for (int next : adj[cur]) {
			if (yx[next] != -1 && label[yx[next]] == INF) {
				label[yx[next]] = label[cur] + 1;
				q.push(yx[next]);
			}
		}
	}
	return;
}

bool dfs(int cur)
{
	for (int next : adj[cur]) {
		if (yx[next] == -1 || (label[yx[next]] == label[cur] + 1 && dfs(yx[next]))) {
			yx[next] = cur;
			xy[cur] = next;
			return true;
		}
	}
	return false;
}
int main()
{
	scanf("%d", &n);
	adj.resize(n + 1);

	for (int i = 1; i <= n; ++i) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		if (t1 != t2) {
			adj[i].push_back(t1);
			adj[i].push_back(t2);
		}
		else
			adj[i].push_back(t1);
	}

	xy.resize(n + 1, -1);
	yx.resize(1000001, -1);
	label.resize(n + 1);

	while (1) {
		bfs();
		int flow = 0;
		for (int i = 1; i <= n; ++i)
			if (xy[i] == -1 && dfs(i))
				flow++;
		if (flow == 0)	break;
		match += flow;
	}

	if (match < n)
		printf("-1\n");
	else
		for (int i = 1; i <= n; ++i) 
			printf("%d\n", xy[i]);
	
	return 0;
}

6. 결과

 

지적, 댓글 환영입니다~.