UVa OJ 12118 - Inspector's Dilemma

문제 링크

\(1\leq{V}\leq{10^3}\)

\(1\leq{E}\leq{V\cdot(V-1)/2}\)

\(1\leq{T}\leq{10}\)

도시의수 V와 검사해야 할 도로의 수 E가 주어지고, E개의 줄에 대해 도로가 잇는 두 도시 a b 가 주어진다.

모든 두 도시 간에는 도로가 있으며, 각 도로를 지나는데 드는 시간은 T이다.

도로를 검사하는 검사자가 주어진 E개의 도로를 모두 지나야 한다. 이 때 최소 시간을 구하는 문제이다.

모든 엣지의 가중치가 T로 같은 것이기 때문에 이 문제는 결국 최소의 간선을 지나면서 주어진 간선을 모두 지나는

문제를 풀고 T를 곱하면 된다. 최소의 간선을 지나려면 주어진 간선들을 딱 한번씩만 지나고

주어진 간선 외의 간선은 가능한한 지나지 않으면 될 것이다. 주어진 간선만을 한번씩만 지나 모든 간선을 방문한다는

말은 결국 주어진 도로로 그래프를 형성했을 때 이 그래프의 오일러 경로가 존재하여야 한다라는 말과 같다.

이어진 K개의 도로들이 오일러 경로를 이룬다면 이 때 지나야만 하는 도로의 수는 딱 K개 일 것이다.

그리고 주어진 도로들로 그래프를 형성하였을 때 여러개의 컴포넌트가 있을 텐데 각각의 컴포넌트가 모두 오일러 경로가

존재한다면 각 컴포넌트마다 컴포넌트에 포함된 간선의 수 만큼 지나야하고 다 지난 뒤에 다른 컴포넌트로

넘어가야 하기때문에 1개를 더 지나야 하기 때문에 답은 E+(컴포넌트의 수-1) 일 것이다.

하지만 각 컴포넌트 중에 오일러 경로가 존재하지 않는 그래프가 있다면 어떻게 될까?

답은 각 컴포넌트마다 반드시 지나야만 하는 최소 간선들을 정해서 그래프에 포함시켜

모든 컴포넌트가 오일러 경로가 존재하도록 만든 뒤에 위에서 말했던 풀이로 풀면 될 것이다.

그럼 어떤 connected graph 가 주어졌을 때 이 그래프가 오일러 경로를 갖도록 추가해야 하는 간선의 최소 수는 몇일까?

일단 오일러 경로를 가지기 위한 조건은 두가지가 있다.

1. 모든 노드의 degree가 짝수

2. 딱 두 노드의 degree만 홀수이고 나머지는 다 짝수

그럼 degree가 홀수인 노드가 없다면 이미 오일러경로가 존재하고, 3개 이상이라면 2개 이하로 줄여줘야 하는데

degree가 홀수인 두 노드를 새로운 간선으로 이어준다면 홀수 degree 노드가 2개 줄어든다는 것을 이용해

간선을 (홀수degree수-2)/2 만큼 추가해준다. 그럼 최종적으로 홀수 degree의 노드 수가 1개 또는 2개가 남을 것이다.

2개가 남는다면 오일러 경로가 존재하게 되므로 다음 컴포넌트로 넘어가서 똑같이 계산하면 되고 1개가 남을 땐

어떻게 할까? 1개가 남았다는 것은 애초에 홀수 degree 의 수가 홀수개가 있었다는 말인데,

그래프에서 홀수 degree의 수는 무조건 짝수개라는 것이 증명이 되어있다.

그렇기 때문에 애초부터 홀수degree가 없거나 아니면 2개로 만들어 주기만 하면 된다.

그렇다면 각 컴포넌트 마다 (홀수degree수-2)/2 를 누적해주고 (컴포넌트의 수-1) 를 더해주면 답이다.

+추가 설명

이 문제는 결국 V개의 노드로 이루어진 그래프 G가 주어졌을 때 이 그래프가 오일러 경로를 갖도록 추가하는

간선의 최소 개수를 구하는 방법을 찾는 것과 같다. 왜냐하면 위에서 각 컴포넌트가 오일러 경로를 갖도록 만든뒤

컴포넌트와 컴포넌트를 이어줬는데 이렇게 하면 결국 모든 connected graph 가 오일러 경로를 갖게 되기 때문이다.

그림으로 보면 이해가 쉬울 것이다.

각 컴포넌트의 모든노드가 짝수 degree 이거나 혹은 두개만 홀수 degree 이고 나머지가 짝수 degree 이도록

만들었을 텐데 그러면 컴포넌트와 컴포넌트를 이을 때 홀수 degree 2개가 있는 컴포넌트는 홀수 degree로 잇고,

모두 짝수 degree 인 컴포넌트는 아무 짝수 degree 하나를 잡아서 이으면 결국 시작 컴포넌트의 시작노드와 마지막

컴포넌트의 마지막 노드를 제외한 모든 노드들이 짝수 컴포넌트가 되기 때문에 전체 그래프가 오일러 경로를

갖게 되는 것이다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int G[1003][1003];
int degree[1003];
int V,E,T;
int cntOdd;
int visited[1003];
void dfs(int here){
    visited[here] = 1;
    cntOdd += (degree[here]%2);
    
    for(int there = 1; there <= V; there++){
        if(!G[here][there] || visited[there]) continue;
        dfs(there);
    }
}
int main() {
    for(int t = 1; ; t++){
        scanf("%d%d%d",&V,&E,&T);
        if(!V&&!E&&!T) break;
 
        memset(degree,0,sizeof(degree));
        memset(G,0,sizeof(G));
        memset(visited,0,sizeof(visited));
 
        for(int i = 0 ; i < E; i++){
            int a, b;
            scanf("%d%d",&a,&b);
            G[a][b] = G[b][a] = 1;
            degree[a]++, degree[b]++;
        }
 
        int ans = 0;
        for(int i = 1; i <= V; i++){
            if(visited[i] || !degree[i]) continue;
            ans++;
            cntOdd = 0;
            dfs(i);
            if(cntOdd>=2) ans += (cntOdd-2)/2;
        }
        if(ans) ans--;
        ans+=E;
        printf("Case %d: %d\n",t,ans*T);
 
    }
    return 0;
}