解題區/解題區 - UVa

UVa 265 - Dining Diplomats

contents

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

Problem

有 10 個外交官，各自代表自己的國家，並且也存在他們擅長的語言。現在 10 個外交官圍成一桌，相鄰的兩個外交官必須有相同語言，同時彼此的國家要是邦交關係。

提出一種可行的做法。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF USA GBR FRA FRG
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
TLC ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW
TQA EB TLC DAO PSR FEQ KCW
DAO B TLC TQA FHH FAB PSR FEQ QPA KCW
FHH B TLC DAO PSR KCW
NUW DBE TLC
FAB D TLC DAO PSR FEQ QPA
PSR AC TLC TQA DAO FHH FAB QPA
FEQ CB TLC TQA DAO FAB QPA
QPA D TLC DAO FAB PSR FEQ KCW
KCW AE TLC TQA DAO FHH QPA

Output

1
2
3
4
5
6
7
8
9
10
11
12
1 F USA E
2 E CHN E
3 E GBR E
4 E KOR E
5 E ISR H
6 H JPN G
7 G POR E
8 E FRG R
9 R USR F
10 F FRA F
NO SOLUTION EXISTS

Solution

簡單的銷售員旅遊問題 (TSP: Travelling salesman problem)，這裏使用動態規劃來完成，殺雞用牛刀，窮舉 O(10!) 也許是可行的。定義 dp[2^n][n] = dp[i][j] 表示當前經過的狀態 i，最後停留的點為 j，接著進行轉移，記錄走法。

特別小心有相同國家的外交官，建造相鄰邊時，邦交國中必然有自己國，否則會造成判斷錯誤。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h> 
#include <string.h>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <assert.h>
#include <algorithm>
using namespace std;
struct State {
    string name, lang;
    set<string> g;
    int lang_mask[128];
    int read() {
        string line;
        if (getline(cin, line)) {
            assert(line.length() > 0);
            g.clear();
            stringstream sin(line);
            sin >> name >> lang;
            while (sin >> line)
                g.insert(line);
            
            g.insert(name); // what the fuck, same country in test data.
            memset(lang_mask, 0, sizeof(lang_mask));
            for (int i = 0; i < lang.length(); i++)
                lang_mask[lang[i]] = 1;
            return 1;
        } else {
            return 0;
        }
    }
    int hasCommon(const State &a) {
        for (int i = 0; i < 128; i++)
            if (lang_mask[i] && a.lang_mask[i])
                return 1;
        return 0;
    }
    char common(const State &a) {
        for (int i = 0; i < 128; i++)
            if (lang_mask[i] && a.lang_mask[i])
                return i;
        return '-';
    }
} C[10];
int g[10][10];
int dp[1<<10][10], from[1<<10][10];
int tsp(int u, int last) {
    if (dp[u][last] != -1)	return dp[u][last];
    int &ret = dp[u][last];
    ret = 0;
    for (int i = 0; i < 10; i++) {
        if (((u>>i)&1) && g[last][i]) {
            int f = tsp(u^(1<<i), i);
            if (f) {
                from[u][last] = i;
                return ret = 1;				
            }
        }
    }
    return ret;
}
int main() {
    while (true) {
        for (int i = 0; i < 10; i++) {
            if (!C[i].read())
                return 0;
        }
        
        memset(g, 0, sizeof(g));
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                if (C[i].g.count(C[j].name) && C[j].g.count(C[i].name) 
                    && C[i].hasCommon(C[j])) {
                    g[i][j] = 1;
                }
            }
        }
        
//		for (int i = 0; i < 10; i++, puts(""))
//			for (int j = 0; j < 10; j++)
//				printf("%d ", g[i][j] > 0);
        
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 1;
        int flag = tsp((1<<10)-1, 0);
        if (flag) {
            int p = (1<<10)-1, q = 0;
            int seat[10];
            for (int i = 0; i < 10; i++) {
                seat[i] = q;
                q = from[p][q];
                p = p^(1<<q);
            }
            for (int i = 0; i < 10; i++) 
                printf("%d %c %s %c\n", i+1, C[seat[i]].common(C[seat[(i-1+10)%10]]), 
                    C[seat[i]].name.c_str(), C[seat[i]].common(C[seat[(i+1+10)%10]]));
        } else {
            puts("NO SOLUTION EXISTS");
        }
        puts("");
        
        while (getchar() != '\n');
    }
    return 0;
}
/*
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF USA GBR FRA FRG
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
USA EF CHN GBR USR FRA FRG JPN ISR POR KOR
CHN CFE USA GBR FRA FRG
GBR ER USA CHN USR FRA FRG JPN ISR POR KOR
USR RF
FRA F USA CHN GBR USR FRG JPN ISR POR
FRG ERG USA CHN GBR USR FRA JPN ISR POR
JPN JHG USA GBR FRA FRG JPN ISR POR KOR
ISR HER USA GBR FRA FRG JPN KOR
POR PGE USA GBR FRA FRG JPN
KOR KEC USA GBR USR JPN ISR
TLC ADBE TQA DAO FHH NUW FAB PSR FEQ QPA KCW
TQA EB TLC DAO PSR FEQ KCW
DAO B TLC TQA FHH FAB PSR FEQ QPA KCW
FHH B TLC DAO PSR KCW
NUW DBE TLC
FAB D TLC DAO PSR FEQ QPA
PSR AC TLC TQA DAO FHH FAB QPA
FEQ CB TLC TQA DAO FAB QPA
QPA D TLC DAO FAB PSR FEQ KCW
KCW AE TLC TQA DAO FHH QPA
*/