poj1129 Channel Allocation DFS

题目

题意：给定N个节点，让你对其涂色，使其任何相邻的两个节点颜色不同。

思路：

1. 问题模型是着色问题,枚举颜色的个数, 每次枚举看可以完成全部点的着色.

2. 采用深搜,每一次当前色的种数深搜完毕就加1种，直到全部点都被着色完毕, 这样

从最少的开始深搜,结果出现肯定是最少的。

该题N<26，可以不用四色原理剪枝。

附上一发代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int flag,ans,map[30][30],color[30],n;
 7 char s[40];
 8 int check(int x,int y)         //判断是否存在相邻节点颜色相同 
 9 {
10     for(int i=0;i<n;i++)
11     {
12         if(map[x][i]&&color[i]==y)
13         return 0;
14     }
15     return 1;
16 }
17 void dfs(int a,int b)       //当前搜索到下标为a的节点，此时总共用的色彩数为b
18 {
19     if(flag)
20     return;
21     if(a>=n)                //当所有节点都被着色后，返回
22     {
23     flag=1;
24     return;
25     }
26     for(int i=1;i<=b;i++)        //搜索一种颜色能涂的所有情况 
27     {
28         if(check(a,i))
29         {
30             color[a]=i;
31             dfs(a+1,b);
32             color[a]=0;     //回溯 
33         }
34     }
35     if(!flag)             //当用b种颜色无法完成时，则增加一种颜色进行着色 
36     {
37         ans++;
38         dfs(a,b+1);
39     }
40 }
41 main()
42 {
43     int i,j;
44     while(~scanf("%d",&n)&n)
45     {
46         memset(map,0,sizeof(map));
47         memset(color,0,sizeof(color));
48         for(i=0;i<n;i++)
49         {
50             scanf("%s",s);
51             for(j=2;s[j]!='';j++)      //for(j=2;j<strlen(s);j++)
52             map[s[0]-'A'][s[j]-'A']=1;
53         }
54         flag=0;ans=1;
55         dfs(0,1);
56         if(ans==1)
57         printf("1 channel needed.
");
58         else
59         printf("%d channels needed.
",ans);
60     }
61 }