8088 : Airports

풀이

n개의 노드에 대해, 각 노드의 degree가 주어진다.

주어진 입력에 맞게 그래프를 구성해서 간선들을 출력하는 문제이다.

(불가능한 경우는 주어지지 않는다)

남은 degree의 수가 가장 큰 노드를, 그 다음으로 작은 애들이랑 하나씩 이어주자.

이런 작업을 degree가 0이 될 때까지 반복하자.

다시 말해, degree가 큰 순서대로 먼저 간선을 이어주면 된다.

그럼 된다.

증명(?)

주어지는 그래프는 항상 valid한 그래프이다. 그럼, 완성된 그래프에서 노드를 하나씩 제거한다고 가정해보자. degree가 가장 큰 노드부터 제거해보자.

  1. 그래프 G에서 degree가 가장 큰 노드 하나를 제거해도, G’은 여전히 valid한 그래프이다.
  2. 마찬가지로 G’에 1의 작업을 반복해도, G’‘은 여전히 valid한 그래프이다.
  3. 이 작업을 노드 수가 0이 될 때까지 반복할 수 있다.

이제 간선들을 제거 하지 말고 추가 해보자.

띠용?!

코드

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
int n;
priority_queue<pii, vector<pii>, less<pii> > pq;
vector<int> r[501];
vector<pii> tmp;
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x); pq.push({ x,i });
    }
    while (!pq.empty()) {
        auto a = pq.top(); pq.pop();
        while (a.first--) {
            auto b = pq.top(); pq.pop();
            r[a.second].push_back(b.second);
            if (--b.first) tmp.push_back(b);
        }
        for (pii it : tmp) pq.push(it);
        tmp.clear();
    }
    for (int i = 1; i <= n; i++) {
        for (int j : r[i]) printf("%d %d\n", i, j);
    }
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-27 15:23

Read more posts by this author