본문 바로가기
Problem Solving/ICPC

ACPC 2015 연습 결과 및 H. Capital City 풀이

by hongjun7 2016. 8. 30.

대회 링크 : https://codeforces.com/gym/100676


결과





ACPC 2015 H. Capital City 문제


가중치가 있는 무방향 그래프가 주어진다. 여기서 '사이클'이란, 어느 하나의 간선을 지워도 어떤 정점 u에서 정점 v로의 경로가 존재할 때에 u와 v는 같은 '사이클'에 속한다고 정의한다. 두 정점 사이의 거리는 다음과 같이 정의된다.

1. 두 정점 u와 v가 같은 사이클 내에 속한다면, 둘 사이의 거리는 0이다.

2. 두 정점 u와 v가 같은 사이클 내에 속하지 않는다면, 둘 사이의 거리는 둘 사이를 잇는 최단 경로의 길이이다.

문제에서 요구하는 것은 다음과 같다. f(s)를 정점 s로부터 시작되는 최장 경로로 정의할 때, f(x)=min[f(s)]인 정점의 번호 x를 출력하는 것이다. 그러한 x가 여러 가지가 존재한다면, 정점의 번호가 가장 작은 것을 출력하면 된다.


ACPC 2015 H. Capital City 풀이


사이클은 BCC 알고리즘으로 모든 단절선을 구하여 묶을 수 있다. 단절선들을 제외한 집합에서의 Connected Component들을 묶으면 그 묶음이 하나의 사이클이 된다. 하나의 사이클을 하나의 정점으로 보면, 원래의 그래프는 트리의 형태가 된다. 문제는 트리의 중심이 되는 정점 중 번호를 가장 작은 것을 출력하는 것으로 바뀐다.

트리의 지름을 계산할 때와 비슷한 테크닉을 사용하면 된다. 우선 임의의 정점 v에 대해 자식 노드들로 뻗어나가는 경로 중 가장 길이가 긴 경로를 L(v), 두 번째로 가장 긴 경로를 L2(v)라고 하자. 그리고 부모 노드에서부터 이어지는 가장 긴 경로를 up이라고 하자. v에서의 트리의 반지름은 max(L(v), up)이 된다.


정점 v의 자식 노드 u의 up에 대해 생각해보자. 우선 v에서의 up에다가 dist(u, v)를 더한 값이 될 수가 있다. 그리고 v에서의 L(v) 또는 L2(v)의 에다가 dist(u, v)를 더한 값이 될 수가 있다. L(v)의 경로 상에 u가 속한다면 L2(v)의 값을 취해야겠다.

이제 각 정점마다 해당 정점이 루트가 될 때의 트리의 반지름을 계산할 수 있으니, 최소인 반지름을 가지는 정점에 대해서 번호가 가장 작은 정점을 추출해 출력해주면 된다.


ACPC 2015 H. Capital City 코드



댓글