poj 1129 Channel Allocation

可以转化为着色模型
dfs + 四色定理
 1 #include<cstdio>
 2 #include<memory.h>
 3 int n,num;
 4 int d[100][100];
 5 int c[100];
 6 
 7 bool ok(int step)
 8 {
 9     for(int i = 0; i < n; i++)
10         if(d[step][i] == 1 && c[step] == c[i]) return false;
11     return true;
12 }
13 
14 bool dfs(int num,int step)
15 {
16     if(step >= n) return true;
17     for(int i = 1; i <= num; i++)
18     {
19         c[step] = i;
20         if(ok(step) && dfs(num,step+1)) return true;
21 
22         c[step] = 0;//恢复
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     freopen("input.txt","r",stdin);
30     while(scanf("%d
",&n) && n)
31     {
32         char ch;
33         memset(d,0,sizeof(d));
34         for(int i = 0; i < n; i++)
35         {
36             scanf("%c:",&ch);
37             while(scanf("%c",&ch) && ch != '
')
38                 d[i][ch - 'A'] = d[ch - 'A'][i] = 1;
39         }
40 
41         memset(c,0,sizeof(c));
42         int num = 0;
43         for(num = 1; num < 4; num++)
44             if(dfs(num,0)) break;
45 
46         if(num == 1) printf("1 channel needed.
");
47         else printf("%d channels needed.
",num);
48 
49     }
50     return 0;
51 }