解題區►解題區 - UVa

UVa 12118 - Inspector's Dilemma

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

將一個無向圖中，增加最少條邊，使得可以使用尤拉路徑或環道經過所有條邊。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 3 1
1 2
1 3
4 5
4 4 1
1 2
1 4
2 3
3 4
0 0 0

Sample Output

1
2
Case 1: 4
Case 2: 4

Solution

同一個連通元件中，度數為奇數的點一定為偶數個，保留一組(兩個)奇數點，準備於其他連通元件串起，而其他的則兩兩相接(增加新的邊)，保證每一個點一定能構成偶數度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int parent[1024], weight[1024];
int deg[1024];
int findp(int x) {
    return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)
        return 0;
    if (weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
int main() {
    int cases = 0;
    int N, M, T, x, y;
    while (scanf("%d %d %d", &N, &M, &T) == 3 && N+M+T) {
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, deg[i] = 0;
        
        int component = N;
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            deg[x]++, deg[y]++;
            if (joint(x, y))
                component--;
        }
        
        for (int i = 1; i <= N; i++) {
            if (weight[i] == 1 && findp(i) == i)
                component--;
        }
        int ret = M, odd[1024] = {};
        ret += component > 0 ? component - 1 : 0;
        for (int i = 1; i <= N; i++) {
            if (deg[i]&1)
                odd[findp(i)]++;
        }
        for (int i = 1; i <= N; i++) {
            if (odd[i] >= 4)
                ret += odd[i]/2 - 1;
        }
        printf("Case %d: %d\n", ++cases, ret * T);
    }
    return 0;
}
/*
 5 3 1
 1 2
 1 3
 4 5
 
 4 4 1
 1 2
 1 4
 2 3
 3 4
 0 0 0
 */