Poj1129

小鱼儿 2022-08-05 08:52 187阅读 0赞

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

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

建模：

一个有N个节点的无向图，要求对每个节点进行染色，使得相邻两个节点颜色都不同，问最少需要多少种颜色？

那么题目就变成了一个经典的图的染色问题。

思路：对于这题数据范围很小（节点最多26个），所以使用普通的暴力搜索法即可

对点i的染色操作：从最小的颜色开始搜索，当i的直接相邻（直接后继）结点已经染过该种颜色时，搜索下一种颜色。

就是说i的染色，当且仅当i的临近结点都没有染过该种颜色，且该种颜色要尽可能小。

PS：存储图的时候并没有用矩阵来，而是用的一种类似邻接表的方式，直接每个点的邻接点都保存下来就可以了。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    const int maxn=30;
    
    struct node
    {
        int next[maxn],edge;
    }V[maxn];
    
    int n,ans;
    int color[maxn];
    
    void input()
    {
        memset(V,0,sizeof(V));
        for(int i = 0 ; i < n ; i++)
        {
            char str[maxn];
            scanf("%s",str);
            int len=strlen(str);
            V[i].edge=0;
            for(int j = 2 ; j < len ; j++)
            {
                V[i].next[V[i].edge]=(str[j]-'A'); //无向边
                V[i].edge++;  //相邻顶点的个数
            }
        }
    }
    
    bool charge(int a)
    {
        for(int i = 0 ; i < V[a].edge ; i++)
        {
            if(color[a]==color[V[a].next[i]]&&color[a]!=-1)
                return false;
        }
        return true;
    }
    
    void dfs(int color_num,int ind)
    {
        if(ind==n)
        {
            ans=min(ans,color_num);
            return ;
        }
        for(int i = 0 ; i < color_num ; i++)
        {
            color[ind]=i;//将顶点ind涂为颜色i
            if(charge(ind))   //相邻顶点没有相同的颜色
            {
                //cout<<"ind1 "<<ind<<" color_num1 "<<color_num<<"color[ind1]"<<color[ind]<<endl;
                dfs(color_num,ind+1); //color_num不增加
            }
        }
        color[ind]=color_num;