按A,B,C……的顺序搜索,让每个字母对应一个数,表示到这个字母时可以用的最少的频道,最后一个字母对应的最少的频道即要求的结果, 比如已经搜完了C,C对应的数是m, 轮到搜索D, D从1-m中选一种频道,如果这个频道和与D相关的字母的频道都不同,再往E搜, 如果不存在这样的频道,则D 用m种外的频道, D 对应的最少频道数即m+1。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int a[30][30],b[30],n;
int small = 10000000;
void dfs(int nn,int mm)
{
int i,j,k,g;
k=0;
if(nn==n+1)
{
if(small>mm)small=mm;
return;
}
for(i=1;i<=mm;i++)
{
k=0;g=0;
for(j=0;j<nn;j++)
{
if(a[nn][j])
{
g++;
if(i!=b[j])k++;
}
}
//cout<<"第i中颜色"<<i<<" "<<"第几个"<<nn<<" "<<g<<" "<<k<<endl;
if(k==g)
{
b[nn]=i;
dfs(nn+1,mm);
b[nn]=0;
}
else
{
b[nn]=mm+1;
dfs(nn+1,mm+1);
b[nn]=0;
}
}
}
main()
{
int i,j,k;
char s[200];
while(cin>>n)
{
if(n==0)break;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(i=0;i<n;i++)
{
cin>>s;
int len = strlen(s);
k = s[0]-'A';
for(j=2;j<len;j++)
{
a[k][s[j]-'A']=a[s[j]-'A'][k]=1;
}
}
b[0]=1;
small = 100000000;
dfs(1,1);
if(small==1)
printf("1 channel needed.\n");
else printf("%d channels needed.\n",small);
}
}
分享到:
相关推荐
北大POJ1129-Channel Allocation【四色定理】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1686093
超密集网络中基于着色的动态信道分配算法,刘婷婷,张健明,超密集网络技术将成为未来第五代(5G)移动通信发展的重要研究方向。为了提高超密集网络的频谱效率,协调下行干扰,本文考虑了控制��
Logical Channel Descriptor and Allocation of Logical Channel Numbers
各种资源分配算法实现,这是第二能量熵的matlab代码,有信道编码,调制,信道估计等。
matlab编程环境下独自编的rayleigh信道的程序,运行过,可以用。
电力线载波通信混合型信道分配方法,邹德琴,刘晓胜,与其他通信方式相比,电力线通信具有不可比拟的便利性和广泛性。然而,整个电力线网络共享一个通信信道,这就导致信道资源短缺。
A number of channel allocation schemes have been proposed to fully utilise the wireless bandwidth, but many of them just proposed the channel allocation scheme without presenting a specific channel ...
该段程序时对动态信道分配进行网络仿真的代码
Matching theory for channel allocation incognitive radio networks
Chain store game based channel allocation in cognitive radio system
QoE and Energy Aware Resource Allocation in Small Cell Networks with Power Selection, Load Management and Channel Allocation
A novel channel allocation method, based on optimal golomb ruler, that allows reduction of FWM effect while maintaining bandwidth efficiency, is presented. Simulation is carried out to show ...
Attachment-Learning for Multi-Channel Allocation in Distributed OFDMA-Based Networks
有关于D2D通信中,信道仿真的编程是基于python语言的。
The studies we described in this section are so recent that the many questions they raise have not yet been answered. We can see, though, that there can be different ways to apply reinforcement ...
4.1 The Channel Allocation Problem 4.1.2 Dynamic Channel Allocation in 4.2 Multi
It is important to assess the effect of transmit power allocation schemes on the energy consumption on random cellular networks. The energy efficiency of 5G green cellular networks with average and ...
this program simulate voice channel in wireless system.