博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1129 Channel Allocation (四色定理)
阅读量:6353 次
发布时间:2019-06-22

本文共 1423 字,大约阅读时间需要 4 分钟。

题目:http://poj.org/problem?id=1129

题意:

当一个广播电台在一个非常大的地区,广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而,每个中继器必须慎重选择使用,使相邻的中继器不互相干扰。如果相邻的中继器使用不同的频道,那么就不会相互干扰。

由于无线电频道是一有限的,一个给定的网络所需的中继频道数目应减至最低。编写一个程序,读取一个中继网络,然后求出需要的最低的不同频道数。

View Code
1 #include 
2 #include
3 using namespace std; 4 struct node 5 { 6 int next[27];//后继 7 int num;//后继的个数 8 }point[27]; 9 int main()10 {11 int i,j,n;12 while(scanf("%d",&n)!=EOF)13 {14 if(n==0)15 break;16 getchar();17 for(i=1;i<=n;i++)18 {19 getchar();//节点序号20 getchar();//冒号21 char c;22 point[i].num=1;23 while(scanf("%c",&c),c!='\n')//输入序号的后继24 {25 int u;26 u=c-'A'+1;27 point[i].next[point[i].num]=u;28 point[i].num++;29 }30 }31 //从最小开始染色32 int color[27]={
0};//标记第i个点染的最小颜色33 color[1]=1;34 int max=1;//最大染色数35 for(i=1;i<=n;i++)36 {37 color[i]=n+1;//假设染最大的颜色38 int vis[27]={
0};//标记39 for(j=1;j
j)47 {48 color[i]=j;//更新i节点的颜色,使之最小49 break;50 }51 }52 if(max

 

转载于:https://www.cnblogs.com/wanglin2011/archive/2013/02/19/2916469.html

你可能感兴趣的文章
ubuntu16.04 在线安装docker ce
查看>>
MyEclipse10.0 采用插件方式安装 SVN
查看>>
java集合之ArrayList链表基础
查看>>
zendframework 内置view
查看>>
dirname的用法:获取文件的父级目录路径
查看>>
android 检查网络连接状态实现步骤
查看>>
Java集合类:HashMap (基于JDK1.8)
查看>>
oracle安装
查看>>
一个漂亮的含绝对值积分不等式
查看>>
求幂级数的和函数
查看>>
spring boot - 整合jpa
查看>>
Life
查看>>
特效展示网站
查看>>
让Div浮动层浮在Flash上面下去,div在flash上,层在flash上
查看>>
风暴数码论坛教程--厨房的搭建和简介
查看>>
【操作系统】实验二 作业调度模拟程序 截止完成时间:2016.4.15共3周
查看>>
设备版本,设备号,APP版本,APP名称获取
查看>>
input 选择 全选 反选
查看>>
[LINQ2Dapper]最完整Dapper To Linq框架(三)---实体类关系映射
查看>>
Host基本概念
查看>>