POJ - 1129 Channel Allocation(图着色算法---顺序着色法)

2019/7/21 19:04:30 人评论 次浏览 分类:学习教程

知识共享许可协议 版权声明:署名,允许他人基于本文进行创作,且必须基于与原先许可协议相同的许可协议分发本文 (Creative Commons)

题目链接:https://cn.vjudge.net/contest/311091#problem/L
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

解析:广播站广播需要中继器,每个中继器需要很好的选择频道,相邻的中继器必须使用不同的频道。问最少需要几个频道?N个中继器,第一行与A相邻的中继器,第二行与B相连的中继器,以此类推…

分析:中继器相当于点,频道相当于颜色,相邻的点不能涂同一种颜色,问最少需要几种颜色?

图着色问题求解算法:近似有效算法–-顺序着色算法(与点的着色顺序密切相关)
1)用i表示顶点序号,i=1;
2)用c表示给顶点i着色为第c种颜色,c=1;
3)对第i个顶点着色,考虑相邻顶点是否已经着色,如果都没有就使用第c种颜色,并转下一个顶点。如果相邻顶点已经用了c颜色,这时c++,接着判断。
注意:最坏的情况是i个顶点,用了i种颜色,这个算法的目的是,让i个顶点所使用的的颜色在满足条件的前提下,所使用的的颜色数小于i。

代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c[100];  //求得的顶点着色数和各顶点的颜色
int n,book[100],e[100][100],sum;
void solve(){
    int u;
    for(int i=0; i<n; i++){
        memset(book,0,sizeof(book));
        for(int j=0; j<n; j++)//判断相邻的顶点是否使用颜色
        {
            if(e[i][j]&&c[j]!=-1)
                book[c[j]]=1;
        }
        for(int k=0; k<=i; k++) //对于第i个顶点,最多需要i种颜色
        {
            if(book[k]==0)
            {
                u=k;
                break;
            }
        }
        c[i]=u;//第i个顶点使用第u种颜色
    }
    for(int i=0; i<n; i++)//该算法求得的是最少颜色,所以要找那个最大值
    {
        if(sum<c[i])
            sum=c[i];
    }
    sum++;
}
int main(){
    char a[100];
    while(~scanf("%d",&n)&&n){
        sum=0;
        memset(c,-1,sizeof(c));
        memset(e,0,sizeof(e));
        for(int i=0; i<n; i++){
            scanf("%s",a);
            for(int j=2; j<strlen(a); j++)
                e[i][a[j]-'A']=1;//两个点相邻
        }
        solve();
        if(sum==1)
            printf("%d channel needed.\n",sum);
        else
            printf("%d channels needed.\n",sum);
    }
    return 0;
}

在这里插入图片描述
性格基础是意志力,自律的坚持和创意潜力相形相塑,才可达致拥有挪移心外喧哗的处世心力。自律是铁杵成针的意志功夫。

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->