解題區/解題區 - UVa

UVa 818 - Cutting Chains

contents

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

Problem

有 n 個鐵環，現在已知鐵環之間緊扣在一起，目標要把鐵環串成一鏈，可以選擇將鐵環剪開，隨後再將其串在一起。

找最少剪開的次數。

Sample Input

1
2
3
4
5
6
5 1 2 2 3 4 5 -1 -1
7 1 2 2 3 3 1 4 5 5 6 6 7 7 4 -1 -1
4 1 2 1 3 1 4 -1 -1
3 1 2 2 3 3 1 -1 -1
3 1 2 2 1 -1 -1
0

Sample Output

1
2
3
4
5
Set 1: Minimum links to open is 1
Set 2: Minimum links to open is 2
Set 3: Minimum links to open is 1
Set 4: Minimum links to open is 1
Set 5: Minimum links to open is 1

Solution

n < 15，窮舉哪幾個環需要剪開，接著把這些需要剪開的環先抽出來，查看剩餘的鐵環的情況，必須滿足都是鏈狀，而且連通元件的個數不能大於剪開的個數 + 1，如此一來，在放回剪開的環才能串在一起。

鏈狀的檢查：檢查每一個 node 的 degree 不可大於 2，同時不應該存在環。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int g[16][16], gmask[16];
int visited[16];
int dfs(int u, int p, int open, int n) {
    visited[u] = 1;
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        if (g[u][i] == 0 || i == p)
            continue;
        if (visited[i] || dfs(i, u, open, n))
            return 1;
    }
    return 0;
}
int checkChain(int open, int n) {
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)
            continue;
        int t = gmask[i]^(gmask[i]&open);
        int degree = __builtin_popcount(t);
        if (degree > 2)
            return 0;
    }
    
    int op = __builtin_popcount(open);
    int comp = 0;
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < n; i++) {
        if ((open>>i)&1)	continue;
        if (visited[i] == 0) {
            if (dfs(i, -1, open, n)) // have cycle
                return 0;
            comp++;
        }
    }
    return op >= comp - 1;
}
int main() {
    int cases = 0;
    int n, x, y;
    while (scanf("%d", &n) == 1 && n) {
        memset(g, 0, sizeof(g));
        memset(gmask, 0, sizeof(gmask));
        while (scanf("%d %d", &x, &y) == 2) {
            if (x == -1)	break;
            x--, y--;
            g[x][y] = g[y][x] = 1;
            gmask[x] |= 1<<y, gmask[y] |= 1<<x;
        }
        
        int ret = 0x3f3f3f3f;
        for (int i = 0; i < (1<<n); i++) { // 1: open.
            int op = __builtin_popcount(i);
            if (op >= ret)	continue;
            if (checkChain(i, n))
                ret = min(ret, op); 
        }
        printf("Set %d: Minimum links to open is %d\n", ++cases, ret);
    }
    return 0;
}