poj 1129 Channel Allocation(图着色,DFS)
阅读原文时间:2023年07月09日阅读:1

题意:

N个中继站,相邻的中继站频道不得相同,问最少需要几个频道。

输入输出:

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个点的无向图,对每个点进行染色,相邻的点颜色不得一致,最少需多少种颜色。DFS即可。

代码:

int nmax;
bool mapp[30][30], is[30], coll[30];
int col[30];

void dfs(int u){
mem(coll,false);
rep(i,0,25){
if(u!=i && mapp[u][i] && col[i]){
coll[col[i]] = true;
}
}
rep(i,26,1) if(coll[i]){
nmax = i;
break;
}
rep(i,1,26) if(!coll[i]){
col[u] = i;
nmax = max(nmax,i);
break;
}
rep(i,0,25){
if(u!=i && mapp[u][i] && !col[i])
dfs(i);
}
}

int main(){
int n;
char s[100];

while(scanf("%d",&n),n){  
    mem(mapp,false);  
    mem(is,false);  
    mem(col,0);

    while(n--){  
        scanf("%s",s);  
        int l=strlen(s);  
        is\[s\[0\]-'A'\] = true;  
        rep(i,2,l-1){  
            mapp\[s\[0\]-'A'\]\[s\[i\]-'A'\] = true;  
            mapp\[s\[i\]-'A'\]\[s\[0\]-'A'\] = true;  
            is\[s\[i\]-'A'\] = true;  
        }  
    }

    nmax = 0;  
    rep(i,0,25){  
        if(is\[i\] && !col\[i\]) dfs(i); //对i进行染色,并从i开始把那个集合中的点都染上色  
    }

    if(nmax==1) printf("%d channel needed.\\n",nmax);  
    else printf("%d channels needed.\\n",nmax);  
}  

}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章