Channel Allocation
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 18 Accepted Submission(s) : 7
Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.
Following the number of repeaters is a list of adjacency relationships. Each line has the form:
A:BCDH
which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form
A:
The repeaters are listed in alphabetical order.
Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross.
#include <iostream>
#include<cstdio>
#include <cstring>
using namespace std;
int kiss[][]={};
bool kisscode[][]={};
int n;
int sgin=;
string s; int strbian()//对相邻关系进行识别
{
if(s.length()==)
return ;
char a;
a=s[];
for(int i=;i<s.length();i++){
kisscode[a-'A'][s[i]-'A']=true;
}
return ;
}
bool dfs(int colersum)
{
bool coler[];
memset(coler,true,sizeof(coler));
if(sgin==n+)
return true;
for(int i=;i<n;i++){
if(kisscode[sgin][i])
coler[kiss[sgin][i]]=false;
}
for(int i=;i<=colersum;i++){
if(coler[i]){//找到相邻位置上没有的颜色
for(int j=;j<=n;j++){//将第sgin个位置进行涂色
kiss[j][sgin]=i;
}
sgin++;
bool a=dfs(colersum);
if(a)
return true;
// sgin--;
// for(int j=0;j<=n;j++){
// kiss[j][sgin]=0;
// }
}
}
return false;
} int main()
{
// freopen("input.txt","r",stdin);
while(cin>>n){
if(n==)
break;
memset(kisscode,false,sizeof(kisscode));
memset(kiss,,sizeof(kiss));
sgin=;
for(int i=;i<n;i++){
cin>>s;
strbian();
}
for(int i=;i<=;i++){
bool a=dfs(i);
if(a){
if(i==){//进行输出,一定注意1种和其他的区别
cout<<i<<" channel needed. "<<endl;
break;
}
else{
cout<<i<<" channels needed. "<<endl;
break;
}
}
}
}
return ;
}