問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1129思路:
好題，典型的圖著色問題
首先，對(duì)于鄰接關(guān)系，可以用二維數(shù)組來表示
具有鄰接關(guān)系的節(jié)點(diǎn)不能使用同一種顏色，求所需顏色的最小值
深度優(yōu)先搜索，當(dāng)目前使用顏色個(gè)數(shù)已經(jīng)超過當(dāng)前最優(yōu)解時(shí)進(jìn)行減枝
代碼:
1 #define MAX_NUM 29
2 #define INF 100000
3 int graph[MAX_NUM][MAX_NUM];
4 int color[MAX_NUM];
5 int num, ans;
6
7 void
8 init()
9 {
10 int i, j, len;
11 char conn[MAX_NUM];
12 memset(graph, 0, sizeof(graph));
13 memset(color, -1, sizeof(color));
14 ans = INF;
15 for(i=0; i<num; i++) {
16 scanf("%s", conn);
17 len = strlen(conn);
18 for(j=2; j<len; j++)
19 graph[i][conn[j]-'A'] = 1;
20 }
21 }
22
23 int
24 is_valid(int depth, int cindex)
25 {
26 int i;
27 for(i=0; i<depth; i++)
28 if(graph[depth][i] && color[i]==cindex)
29 return 0;
30 return 1;
31 }
32
33 void
34 dfs(int depth, int used_colors)
35 {
36 int i;
37 if(used_colors >= ans) /* pruning */
38 return;
39 if(depth == num) {
40 ans = used_colors<ans ? used_colors : ans;
41 return;
42 }
43 for(i=1; i<=used_colors; i++) {
44 if(is_valid(depth, i)) {
45 color[depth] = i;
46 dfs(depth+1, used_colors);
47 color[depth] = -1;
48 }
49 }
50 color[depth] = used_colors+1;
51 dfs(depth+1, used_colors+1);
52 color[depth] = -1;
53 }