http://bailian.openjudge.cn/practice/1129/ 搜索问题。用递归超时，直接用模拟法枚举即可3ms AC
AC代码：染色问题。枚举相邻接点的颜色，找到最小可以使本节点染色的颜色，进行染色。
#include <iostream> #include <vector> #include <cstdio> #include <iomanip> #include <cstring> using namespace std; int num; int color[27]; char command[32]; // 存放带冒号的一行输入 struct node { int next[27]; int son_num; // 邻居个数 }; int main() { while(scanf("%d",&num) && num>0) { node n[27]; // 缺少这部初始化，一直WA for(int i=0;i<27;i++) n[i].son_num = 0; memset(color, 0, sizeof(color)); for(int i=0;i<num;i++) { scanf("%s", command); if(strlen(command) == 2) continue; else { for(int j=2;j<strlen(command);j++) { n[command[0]-'A'].next[n[command[0]-'A'].son_num] = command[j]-'A'; n[command[0]-'A'].son_num++; n[command[j]-'A'].next[n[command[j]-'A'].son_num] = command[0]-'A'; n[command[j]-'A'].son_num++; } } } int tot_color = 1; // 总颜色数目 color[0] = tot_color; for(int i=1;i<num;i++) { bool used[27] = {false}; for(int i=0;i<27;i++) used[i] = false; //color[i] = tot_color + 1; color[i] = tot_color+1; for(int j=0;j<n[i].son_num;j++) { if(color[n[i].next[j]]) // 第i个节点的第j个邻居已经染色 { used[ color[n[i].next[j]] ] = true; } } for(int j=1;j<=tot_color;j++)//对颜色进行枚举 { if(!used[j]) { color[i] = j; break; } } if(color[i] == tot_color+1) tot_color++; //if(tot_color < color[i]) // tot_color = color[i]; } if(tot_color == 1) printf("1 channel needed.\n"); else printf("%d channels needed.\n", tot_color); } return 0; }递归搜索代码：对channel进行枚举，能分配就分配。
#include <iostream> #include <vector> #include <cstdio> #include <iomanip> #include <cstring> using namespace std; int num, flag; int map[30][30], vis[30]; char command[32]; // 存放带冒号的一行输入 int can_set(vector<int> v, int index) { for(int i=0;i<v.size();i++) if(map[v[i]][index] > 0) return 0; return 1; } void dfs(int net_num, int channel_num, vector<int> v[], int fail) { if(flag == 1) return; int finished = 1; for(int i=0;i<net_num;i++) { if(vis[i] == 0) { finished = 0; break; } } if(finished == 1) { flag = 1; return; } for(int i=0;i<net_num;i++) { if(vis[i] == 0) { for(int j=0;j<channel_num;j++) { if(can_set(v[j], i)) { fail = 0; v[j].push_back(i); vis[i] = 1; dfs(net_num, channel_num, v, fail); vis[i] = 0; v[j].erase(v[j].end()-1); } } if(fail == 1) // 这个net不能分配到合适的信道，结束 return; } } } int main() { while(scanf("%d",&num) && num>0) { flag = 0; // 清空邻接表 memset(map, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); for(int i=0;i<num;i++) { scanf("%s", command); if(strlen(command) == 2) continue; else { for(int j=2;j<strlen(command);j++) { map[command[0]-'A'][command[j]-'A']++; map[command[j]-'A'][command[0]-'A']++; } } } for(int i=1;i<=4;i++) { vector<int> v[i]; dfs(num, i, v, 1); if(flag == 1) { if(i == 1) printf("1 channel needed.\n"); else printf("%d channels needed.\n", i); break; } } } return 0; }