[ BOJ 1185 ] 유럽여행

링크

http://icpc.me/1185

문제

1. 모든 마을을 최소 한 번씩은 방문해봐야 한다.

2. 반드시 출발한 곳으로 돌아와야 한다.

3. 출발점은 "임의로" 설정할 수 있다.

이 때 최소 코스트를 출력하라

풀이

핵심은 "다시 돌아와야 한다"라는 것이다.

일단, 출발점은 임의로 설정할 수 있고, MST 특성 상 어떤 곳에서 시작해도 상관이 없음을 생각하면

그냥 그리디스럽게 방문할 때 가장 작은 코스트가 드는 곳에서 시작하면 된다.

예제를 생각해보면, 4번 마을을 방문할 때 코스트가 6으로 제일 적으므로 4번에서 시작하는 것이다.

이제 어떻게 방문할지를 생각해봐야 한다.

관찰을 해보면, 다시 자기자신으로 돌아와야 한다는 특징 때문에, 간선을 무조건 "짝수"번 들러야 함을 알 수 있다.

MST 특성 상 사이클은 없으므로, 시작점 A에서 임의의 정점 A'에서 돌아오는 방법은 A->A'의 경로를 역순으로 오는 방법밖에 없다.

만약, 문제에서 마을을 방문할 때 가격이 추가가 안된다면 그냥 최소 스패닝 트리 구해가지고 가격 2배하면 된다.

하지만... 마을을 방문할 때 가격이 추가 된다...

따라서 다른 방법을 생각해야 한다.

앞의 발상을 좀 바꿔보자.

우리는 $a\leq b$이면 $2a\leq2b$가 됨이 자명하다.

즉, 스패닝 트리를 다 구해서 2배 하는 것이 아니라, 그냥 간선의 코스트 가격을 2배 하고 그 상황에서 MST를 구해도 큰 문제가 없다!

이를 응용해보자!

마을을 방문할 때 방문 정점의 가격을 추가해야함을 생각하고, 우리는 왕복했을 때의 가격을 한꺼번에 더해주므로

!!간선의 코스트를 $2\times cost[s][e]+visit[s]+visit[e]$로 설정해야한다

이 때, cost[s][e]는 s에서 e까지 가는데 소요되는 가격, visit[s]는 s 마을에 방문할 때 드는 cost(갔다가 오는 경우), visit[e]는 e 마을에 방문할 때 드는 cost(가는 경우)이다.

정확하게 풀어쓰면 $cost[s][e]+visit[e]$(S -> E)와 $cost[s][e]+visit[s]$ (E->S)이다.

간단하게 이렇게 간선 설정하고 MST 돌리면 된다. (필자는 크루스칼을 돌렸다)

코드

#include <bits/stdc++.h>
using namespace std;
int par[10005], rnk[10005], vs[10005];
void init()
{
  for(int i=0;i<10005;i++) par[i]=i;
}
struct edge{
  int s, e;
  int cost;
};
 
bool compare(const edge &a, const edge &b)
{
  return a.cost < b.cost;
}
 
int root(int x)
{
  if(par[x]==x) return x;
  return par[x]=root(par[x]);
}
 
int lookup(int x, int y)
{
  return root(x)==root(y);
}
 
void merge(int x, int y)
{
  x=root(x), y=root(y);
  if(x==y) return;
  if(rnk[x]<rnk[y]) swap(x,y);
  if(rnk[x]==rnk[y]) rnk[x]++;
  par[y]=x;
}
 
vector<edge> ro;
 
int main()
{
  init();
  int n,m, mni=-1, mnv=1005;
  scanf("%d %d",&n,&m);
  for(int i=0;i<n;i++)
  {
    scanf("%d",&vs[i]);
    if(mnv>vs[i]) mnv=vs[i], mni=i;
  }
  for(int i=0;i<m;i++)
  {
    int st, en, d;
    scanf("%d %d %d",&st, &en, &d);
    st--, en--;
    d*=2, d+=vs[st], d+=vs[en];
    ro.push_back({st, en, d});
  }
  sort(ro.begin(), ro.end(), compare);
  int ret=0, sz=ro.size();
  for(int i=0;i<sz;i++)
  {
    auto v=ro[i];
    if(lookup(v.s, v.e)) continue;
    ret+=v.cost;
    merge(v.s, v.e);
  }
  return !printf("%d",ret+mnv);
}