가중치가 있는 무방향 그래프가 주어진다. 여기서 '사이클'이란, 어느 하나의 간선을 지워도 어떤 정점 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 코드
#include<stdio.h>#include<vector>#include<map>#include<set>#include<algorithm>usingnamespace std;typedeflonglong ll;#define MN 100005int n, m, dfn[MN], low[MN], cnt;
vector <int> v[MN], c[MN], g[MN], G[MN],Gc[MN];void go(int u,int par){
dfn[u]= low[u]=++cnt;for(int i = v[u].size()-1; i >=0; i--){int w = v[u][i];if(par != w && dfn[w]< dfn[u]){if(dfn[w]<0) go(w, u);
low[u]= min(low[u], low[w]);}elseif(w != par) low[u]= min(low[u], dfn[w]);}}
map <pair<int,int>,int> e,Edge;set<pair<int,int>> ce;intgroup[MN], gn, gminvertex[MN];void dfs(int x){for(auto&y : g[x]){if(group[y])continue;group[y]=group[x];if(gminvertex[group[y]]> y) gminvertex[group[y]]= y;
dfs(y);}}
ll longest[MN], longwho[MN], longest2[MN], long2who[MN];void dfs2(int x,int pa){for(int i =0; i < G[x].size(); i++){int y = G[x][i];int w =Gc[x][i];if(y == pa)continue;
dfs2(y, x);if(longest[x]< longest[y]+ w){
longest2[x]= longest[x];
long2who[x]= longwho[x];
longest[x]= longest[y]+ w;
longwho[x]= y;}elseif(longest2[x]< longest[y]+ w){
longest2[x]= longest[y]+ w;
long2who[x]= y;}}}
ll mindiameter;int rescity;void dfs3(int x,int pa, ll up){
ll diameter = max(up, longest[x]);if(mindiameter ==-1|| mindiameter > diameter){
mindiameter = diameter;
rescity = gminvertex[x];}for(int i =0; i < G[x].size(); i++){int y = G[x][i];int w =Gc[x][i];if(y == pa)continue;
ll val = y == longwho[x]? longest2[x]: longest[x];
dfs3(y, x, max(up, val)+ w);}}int main(){int T;for(scanf("%d",&T); T--;){
scanf("%d%d",&n,&m);for(int i =1; i <= m; i++){int a, b, z;
scanf("%d%d%d",&a,&b,&z);
v[a].push_back(b); v[b].push_back(a);
e[{a, b}]++; e[{b, a}]++;if(Edge.count({ a,b }))Edge[{a, b}]=Edge[{b, a}]= min(Edge[{a, b}], z);elseEdge[{a, b}]=Edge[{b, a}]= z;}for(int i =1; i <= n; i++) dfn[i]=-1;for(int i =1; i <= n; i++)if(dfn[i]<0){ cnt =0; go(i,0);}for(int i =1; i <= n; i++){for(int j = v[i].size()-1; j >=0; j--){if(dfn[i]< dfn[v[i][j]]&& low[v[i][j]]> dfn[i]&& e[{i, v[i][j]}]<=2){
ce.insert({ i, v[i][j]});
ce.insert({ v[i][j], i });}}}for(int i =1; i <= n; i++){for(int j =0; j < v[i].size(); j++){if(ce.count({ i, v[i][j]}))continue;
g[i].push_back(v[i][j]);}}
gn =0;for(int i =1; i <= n; i++){if(group[i])continue;group[i]=++gn;
gminvertex[gn]= i;
dfs(i);}for(auto&E : ce){int x =group[E.first], y =group[E.second];
G[x].push_back(y);Gc[x].push_back(Edge[{E.first, E.second}]);}
dfs2(1,0);
mindiameter =-1, rescity =-1;
dfs3(1,0,0);
printf("%d %I64d\n", rescity, mindiameter);
e.clear(); ce.clear();Edge.clear();for(int i =1; i <= n; i++) v[i].clear(), c[i].clear(), g[i].clear(), G[i].clear(),Gc[i].clear();for(int i =1; i <= n; i++){group[i]= gminvertex[i]=0;
longest[i]= longest2[i]= longwho[i]= long2who[i]=0;}}}
댓글