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

logic_nut

于 2009-08-10 08:15:00 发布

阅读量1.3k

点赞数

分类专栏：搜索经典文章标签： allocation ini

本文链接：https://blog.csdn.net/logic_nut/article/details/4429390

版权

经典同时被 2 个专栏收录

83 篇文章

订阅专栏

搜索

15 篇文章

订阅专栏

本文介绍了一种解决图着色问题的方法，通过使用深度优先搜索（DFS）结合剪枝策略来确定最少需要几种颜色才能使得图中相邻节点不使用相同颜色。该算法实现了0ms的高效运行。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

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

深搜+一点点简单的剪枝，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; }