[ICPC 본선 대비 뇌셋] Day 4

백준 19619번 자매도시 www.acmicpc.net/problem/19619

19619번: 자매 도시

두 간선을 거리 w로 정렬한 뒤 하나씩 추가해나가면서 문제를 해결하면 된다. 역시 보물찾기를 보고 나니 다른 문제들이 쉬워보인다.

편의상 라인을 일렬로 연결된 그래프라고 부르자.

w의 크기순으로 j번째 간선(거리 v[j]라고 하자)까지 연결했다고 하자 연결된 간선들이 라인이 아니면, 연결된 정점들끼리는 모두 왕래가 가능하다. 따라서 연결됨에 따라 집합으로 묶고, 그 집합이 라인이 아니면 있는지를 확인하면 된다. 오프라인 쿼리라면 Union Find로 MlgN만에 풀이를 완성시킬 수 있지만 이 풀이는 생략한다.

온라인 쿼리를 완성시키기 위해서는 적절한 전처리를 하면 된다. 간선이 추가됨에 따라 어떤 그룹이 라인이 아니게 된다면, 그 경우에 새로 왕래할 수 있는 주어진 쿼리의 경로에서 필요한 기름통의 크기는 w가 될것이다. 이제 각 그룹을 다음과 같이 관리한다.

[전처리]

각 정점는 int rootnow, bool notline, vector<pii> root_weight을 가지고 있다. 

간선을 길이순으로 정렬한 후 다음 전처리를 진행한다.

거리가 W인 간선 ab를 추가한다면,

1. a, b가 다른 그룹에 있고, 일반성을 잃지 않고 a의 그룹 A보다 b의 그룹 B의 크기가 작으면, 그룹 B의 원소들의 루트를 모두 그룹 A의 루트로 설정하고, 그룹 B의 모든 정점의 rootnow를 A의 루트로 설정한다.

2. 그룹 A의 루트에 라인인지 아닌지를 판단하는 변수인 notline을 갱신한다.

3. 만약 각 그룹이 라인이 아니게 되었다면, root_weight 벡터에 (rootnow, W)를 push_back하고, root정점의 notline을 true로 지정한다.

 

[시간복잡도 분석]

notline: 각 정점당 최대 한번 O(N)

각 정점의 root와 wegith의 갱신은 최대 lgN: O(NlgN)

 

[쿼리] 정점 a, b

주어지는 쿼리에서 a, b정점의 root_weight 벡터를 앞에서부터 weight 순으로 탐색하여 root가 처음으로 같아질 때의 W의 최솟값이다. root가 같아지지 않는다면 -1을 출력한다.

[시간복잡도 분석]

각 정점에 대해 root_weight의 크기는 lgN이므로 최대 O(lnN)번 탐색: O(NlgN)

 

시험기간이라서 풀이를 띄엄띄엄 올린다... 오늘도 열통시험을 죽쒀서 기분이 우울한데 풀이를 쓰니까 좀 나아진것 같아서 다행이다ㅋㅋ