BOJ 15475 - A pie for a pie (이분그래프, 이분탐색)

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

유사코 골드.

 

<문제설명>

bessie와 elsie가 서로 선물을 교환한다. 같은 선물에 대해 각자 생각하는 가치가 다를 수 있다.

 

최대 1e5개의 선물을 둘이 같은 개수만큼 가지고 있다. 서로 선물을 교환하려 한다.

 

예를들어, bessie가 볼때 3의 가치를 지닌 선물을 bessie가 받은 경우 3이상 3+d이하(bessie기준)선물을 elsie에게 보답으로 준다. elsie도 마찬가지다. 이런 방법으로 계속 선물을 교환할 때, 본인이 생각했을 때 가치가 0인 선물을 받으면 성공적으로 선물 교환이 이뤄진 것으로 본다.

 

bessie부터 선물을 주기로 한다. bessie의 i번째 선물을 처음으로 elsie에게 줬을 때 가장 적은 횟수로 성공적인 선물교환이 이뤄지면 몇번 선물을 주고받아야 하는지 n줄에 걸쳐 출력한다.

 

<풀이>

최대 2*n개의 선물이 있다. 선물마다 bessie가 생각하는 가치와 elsie가 생각하는 가치를 따로 저장한다.

bes[i] : bessie가 생각하는 i번째 선물의 가치

els[i] : elsie가 생각하는 i번째 선물의 가치

 

0번 선물에서 시작하여 n-1번 선물까지 각각 bfs를 돌면서 최단경로를 찾으면 n*O(nlogn: 이분그래프 bfs)이므로 tle.

 

도착점을 기준으로 (bes가 elsie에게 가치0을 선물할 때, elsie가 bes에게 가치0을 선물할 때) multisource floodfill하면 O(nlogn)에 풀 수 있다.

 

source를 큐에 넣어주면, 그 source는 더이상 다른 정점과 이어줄 필요가 없으므로 유효한 정점에 넣지 않는다.

for (int i = 0; i < n; i++) {
	if (els[i] == 0) q.push(i), dist[i] = 1;
	else ValidBessie.insert(i);
	if (bes[n + i] == 0) q.push(n + i), dist[n + i] = 1;
	else ValidElsie.insert(n + i);
}

 

bfs과정에서, bessie가 elsie에게 선물을 받는 상황을 생각해보자.(지문과 거꾸로 접근하기 때문에 선물을 받는 상황을 생각해야 한다.

예를들어, d=1일 때 bessie가 생각했을 때 5인 선물을 받았다면 elsie는 (bes기준) 5이하 중 5-d 이상인 선물을 보냈을 것이다.

//ValidElsie는 bessie가 생각하는 가치 기준으로 적절히 정렬됨.
//유효한 elsie선물 중 bessie가 생각하는 i번 선물의 가치(bes[i]) 이하 최대 선물
auto itE = ValidElsie.lower_bound(i);
//그런 선물이 없거나 가치가 너무 크다면 더이상 이을 간선이 없음.
if (itE == ValidElsie.end() || bes[*itE] - d > bes[i]) break;
dist[*itE] = dist[i] + 1;
q.push(*itE);
ValidElsie.erase(itE); //이분그래프의 bfs가 VlogV가 되는 이유

 

<코드>

int n, d;
int bes[2 * MAX]; //bessie가 볼 때 가치
int els[2 * MAX]; //elsie가 볼 때 가치
int dist[2 * MAX];

struct cmpA {
	bool operator()(int a, int b) const {
		return els[a] < els[b];
	}
};

struct cmpB {
	bool operator()(int a, int b) const {
		return bes[a] < bes[b];
	}
};

//다른 정점과 이어질 여지가 있는 정점
multiset<int, cmpA> ValidBessie; //elsie->bessie 유효한 bessie 정점
multiset<int, cmpB> ValidElsie; //bessie->elsie 유효한 elsie 정점

int main() {
	cin >> n >> d;
	for (int i = 0; i < 2 * n; i++) {
		cin >> bes[i] >> els[i];
		bes[i] = -bes[i], els[i] = -els[i];
		dist[i] = -1;
	}

	queue<int> q;

	for (int i = 0; i < n; i++) {
		if (els[i] == 0) q.push(i), dist[i] = 1;
		else ValidBessie.insert(i);
		if (bes[n + i] == 0) q.push(n + i), dist[n + i] = 1;
		else ValidElsie.insert(n + i);
	}

	while (!q.empty()) {
		int i = q.front(); q.pop();
		if (i < n) {
			while (true) {
				auto itE = ValidElsie.lower_bound(i);
				if (itE == ValidElsie.end() || bes[*itE] - d > bes[i]) break;
				dist[*itE] = dist[i] + 1;
				q.push(*itE);
				ValidElsie.erase(itE);
			}
		}
		else {
			while (true) {
				auto itB = ValidBessie.lower_bound(i);
				if (itB == ValidBessie.end() || els[*itB] - d > els[i]) break;
				dist[*itB] = dist[i] + 1;
				q.push(*itB);
				ValidBessie.erase(itB);
			}
		}
	}
	for (int i = 0; i < n; i++)
		cout << dist[i] << '\n';
}

 

 

<생각>

가중치 1인 이분그래프에서 bfs로 최단경로 -> O(VlogV)가 가능하다는 사전지식

 

유효한 간선을 모두 이어놓고 시작할 수 없음 -> bfs과정에서 유효한 간선을 이분탐색을 이용해서 로그시간에

문제 안내대로가 아닌 도착점으로부터 거꾸로 최단경로를 짜야 함.

 

multiset<int, cmp> a,b로 이분그래프의 부분을 두 부분으로 나눌 것. set을 쓰지 않는 이유는 어떤 두 선물에 대해 가치가 같을 수 있기 때문. set에서 사용자지정 비교함수쓰는법 유념

 

+ 구현어려움