首页 > 代码库 > poj1129 Channel Allocation（染色问题）
poj1129 Channel Allocation（染色问题）
题目链接：poj1129 Channel Allocation
题意：要求相邻中继器必须使用不同的频道，求需要使用的频道的最少数目。
题解：就是求图的色数，这里采用求图的色数的近似有效算法——顺序着色算法（实质是一种贪心策略：在给任何一个顶点着色时，采用其邻接顶点中没有使用的，编号最小的颜色）。
注：中继器网络是一个平面图，即图中不存在相交的边。
看讨论后发现这组数据，AC代码没过orz：
6
A:BEF
B:AC
C:BD
D:CEF
E:ADF
F:ADE 正确答案应该是3 ： A(1)B(2)C(3)D(1)E(2)F(3)但是AC的代码得出了错误答案4
数据弱啊ORZ。。。。。。
顺序着色算法（有问题的AC代码，毕竟这是求近似解，不能保证解最优）：
1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #define CLR(a,b) memset((a),(b),sizeof((a))) 7 using namespace std; 8 9 const int N = 26;10 11 char s[N];12 int g[N][N];13 int n, ans;14 bool vis[N]; //每种颜色的使用标记15 int color[N]; //各顶点的颜色16 void greedy(){17 int i, j;18 for(i = 0; i < n; ++i){19 CLR(vis,0);20 for(j = 0; j < n; ++j){21 if(g[i][j] && color[j] != -1){//邻接顶点j已经着色22 vis[color[j]] = 1;23 }24 }25 for(j = 0; j <= i; ++j){26 //j为顶点i的所有邻接顶点中没有使用的，编号最小的颜色27 if(!vis[j])break;28 }29 color[i] = j;//给i着色第j种颜色30 }31 for(i = 0; i < n; ++i)32 if(color[i] > ans)33 ans = color[i];34 ans++;35 }36 int main(){37 int i, j, l;38 while(~scanf("%d", &n),n){39 CLR(g,0);40 ans = 0;41 for(i = 0; i < n; ++i)42 color[i] = -1;43 for(i = 0; i < n; ++i){44 scanf("%s", s);45 l = strlen(s) - 2; //与第i个中继器相邻的中继器数目46 for(j = 0; j < l; ++j){47 g[i][s[j+2]-‘A‘] = 1;48 g[s[j+2]-‘A‘][i] = 1;49 }50 }51 greedy();52 if(ans == 1)53 printf("%d channel needed.\n", ans);54 else55 printf("%d channels needed.\n", ans);56 }57 return 0;58 }
在网上搜了一下，找到个正确的AC代码，用四色定理加深搜可解：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define CLR(a,b) memset((a),(b),sizeof((a))) 5 using namespace std; 6 const int N = 26; 7 8 char s[N]; 9 int n, ans;10 int color[N];11 bool g[N][N];12 bool jud(int x, int c){13 for(int i = 0; i < n; ++i)14 if(i != x && g[x][i] && color[i] == c)15 return 0;16 return 1;17 }18 void dfs(int x){19 if(x == n){20 ans = min(ans, *max_element(color, color + n));21 return;22 }23 for(int i = x; i < n; ++i){24 for(int j = 1; j <= 4; ++j){25 if(jud(i, j)){26 color[i] = j;27 dfs(i + 1);28 }29 }30 }31 }32 int main(){33 int i, j, l;34 while(~scanf("%d",&n),n){35 CLR(g,0);36 CLR(color,0);37 color[0] = 1;38 ans = 4;39 for(i = 0; i < n; ++i){40 scanf("%s", s);41 l = strlen(s) - 2;42 for(j = 0; j < l; ++j){43 g[i][s[j+2]-‘A‘] = 1;44 g[s[j+2]-‘A‘][i] = 1;45 }46 }47 dfs(1);48 if(ans == 1)49 printf("%d channel needed.\n", ans);50 else51 printf("%d channels needed.\n", ans);52 }53 return 0;54 }
poj1129 Channel Allocation（染色问题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。