【基础练习】【DFS】poj1129 Channel Allocation题解

向右看齐 2022-08-09 14:57 127阅读 0赞

Channel Allocation

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;13398</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;6858</td> 
  </tr> 
 </tbody> 
</table>

Description

When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels.   
  
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.

Input

The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input.   
  
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.

Output

For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.

Sample Input

2
    A:
    B:
    4
    A:BC
    B:ACD
    C:ABD
    D:BC
    4
    A:BCD
    B:ACD
    C:ABD
    D:ABC
    0

Sample Output

1 channel needed.
    3 channels needed.
    4 channels needed.

Source

[Southern African 2001][]

必要条件的简单翻译：

相邻中继器使用不同频道  
写一个程序读取中继网络的描述 确定所需频道最小是多少个  
  
  
输入 多组数据代表多个地图  
每一组数据 第一行是一个数字 表示中继器的数量 1到26个  
中继器由A开始的连续的大写字母表示  
  
  
接下来是一份相邻关系表 每一行格式类似于A:BCDH 表示后面这四个点和A相邻 如果是A:  这样的表示没有相邻的点 按字母表顺序输入  
注意 相邻关系是双向的 且由于中继器在一个平面上，不存在相互交叉的线段  
  
  
输入以0结尾（整个输入文件的结尾）  
  
  
输出  
对于每组数据，输出仅一行，为需要的最小频道数 按格式输出 注意单复数  
  
  
  
简而言之，一张图，如果两节点有边就不能用同一个颜色染色  
  
由于不存在交叉的线段(这个我至今还不大理解，但大家画出来图看一看吧，大概就懂了) 四色定理要求每两个国家至少有一条相邻边，也就是说，在一张地图上不可能有五个国家**两两接壤 **这正好与“不存在交叉的线段”对应。画出图来大家就会发现，五个以上的点不可能在变不交叉的情况下完全联通。

因此这道题目可以用四色定理剪枝，数组可以只开到5

有人用枚举过，这题我用的搜索。

POJ没问题，但online judge数据有问题，需要重复加边。如果NOI online judge的同学们得了五分，加边时改为加两条即可。

//POJ1129 Channel Allocation 暴搜 四色剪枝
    //copyright by ametake
    #include
       
        
    #include
        
          
    #include
         
          
    using namespace std;
    
    const int maxn=30;
    const int maxm=700+10;
    bool ok[30],vis[30];
    int hd[maxn],t[maxm*2],nxt[maxm*2],et;
    int color[maxn];
    int n,ans;
    char s[40];
    
    void add(int x,int y)
    {
        et++;
        t[et]=y;
        nxt[et]=hd[x];
        hd[x]=et;
    }
    
    void dfs(int i)
    {
        for (int j=hd[i];j!=-1;j=nxt[j])
        {
            if (vis[t[j]]) ok[color[t[j]]]=true;
        }
        for (int j=1;j<=26;j++) if (!ok[j])
        {
            color[i]=j;
            ans=max(ans,j);
            break;
        }
        for (int j=hd[i];j!=-1;j=nxt[j])
        {
            if (!vis[t[j]])
            {
                memset(ok,false,sizeof(ok));
                vis[t[j]]=true;
                dfs(t[j]);
            }
        }
    }
    int main()
    {
        freopen("1.txt","r",stdin);
        freopen("2.txt","w",stdout); 
        gets(s);
        sscanf(s,"%d",&n);
        while (n!=0)
        {
            memset(hd,-1,sizeof(hd));
            memset(t,-1,sizeof(t));
            et=0;
            memset(color,0,sizeof(color));
            for (int i=1;i<=n;i++)//建图 
            {
                gets(s);
                int j=2;
                while (s[j]!='\0')
                {
                    int x=s[j]-'A'+1;
                    add(i,x);
                    j++;
                }
            }
            ans=0;
            for (int i=1;i<=et;i++) printf("%d %d %d\n",i,t[i],nxt[i]);
            memset(vis,false,sizeof(vis));
            for (int i=1;i<=n;i++) if (!vis[i])
            {
                memset(ok,false,sizeof(ok));
                vis[i]=true;
                dfs(i);
            }
            if (ans==1) printf("1 channel needed.\n");
            else printf("%d channels needed.\n",ans);
            gets(s);
            sscanf(s,"%d",&n);
        }
        return 0;
    }

因为下面这句诗，看了一下宋之问，这个不大有名气的诗人。武则天时期，还算是初唐。宋氏三兄弟各有所长。宋之问也算是奇奇怪怪却又觉得了无遗憾的一生吧。不知道该怎么评价。一卷风烟历史已去，这话说的苍凉，然而这些事情究竟是怎样又有谁知道呢。或许是同宗同族的缘故，跨越千年终归对这个古人有些奇妙的关切之感。

——去年上巳洛桥边，今年寒食庐山曲

[Southern African 2001]: http://poj.org/searchproblem?field=source&key=Southern+African+2001