pku 1129 Channel Allocation(回溯（经典的图着色问题）)

构图，如果两点互相影响，则连接一条边。

剩下的就是图着色问题，相连的点不能用同一种颜色，问最少需要多少颜色。

深搜+一点点简单的剪枝，0ms

#include <iostream> using namespace std; bool map[26][26]; int n,ans; int color[26]; bool check(int position,int color_index) { for(int i=0;i<n;i++) { if(map[position][i]&&color[i]==color_index) return false; } return true; } void DFS(int index,int used_color_num) { if(used_color_num>=ans) return; if(index==n) { ans=used_color_num; return; } for(int i=1;i<=used_color_num;i++) { if(check(index,i)) { color[index]=i; DFS(index+1,used_color_num); color[index]=0; } } used_color_num++; color[index]=used_color_num; DFS(index+1,used_color_num); color[index]=0; } int main() { char temp_str[30]; while(scanf("%d",&n)&&n) { memset(map,0,sizeof(map)); memset(color,0,sizeof(color)); ans=INT_MAX; for(int i=0;i<n;i++) { scanf("%s",temp_str); for(int j=2;temp_str[j]!='/0';j++) { map[i][temp_str[j]-'A']=true; } } DFS(0,0); if(ans==1) printf("%d channel needed./n",ans); else printf("%d channels needed./n",ans); } return 0; }