当前位置：首页 > news >正文

【dfs爆搜】poj 1129 Channel Allocation

news 来源：原创 2024/4/29 3:49:16

1129 -- Channel Allocation (poj.org)

题意：

大致的题意就是给你一张图，给这张图染色，最多能染多少种颜色

思路：

首先要构造状态图，构造完状态图之后对其进行搜索（注意是先有图再有的dfs，而不是边dfs边构图，这个是观念的变化）

我们考虑一个状态图的顶点为一个染色方案

类似于这样，这是状态图的一个顶点

一开始的顶点里面的图是一个都没染色的，然后从起点开始转移出去26条边，深度为1的点里面的图是一个点染成26种颜色的情况

这样我们脑子里的图就构造好了，我们去在这个状态图里面dfs，dfs的深度就是顶点里的图已经被染色的点的个数，所以出口就是dep>n

然后对于状态图的一个顶点，我们去枚举状态图的顶点中的图的其中一个顶点的颜色，并用数组标记（注意在状态图里的顶点可能是乱序遍历到的，即有可能是东染一个，西染一个，这个由题目给出的图本身决定

枚举颜色后，我们去check这个颜色是否合法，那只需要遍历这个点相邻的点，看有没有相邻点的颜色相同，若存在颜色相同的点就不合法

我的写法就是用链式前向星存题目里给出的图

Code：

#include <stdio.h>
#define max(a,b) (a>b?a:b)
using namespace std;
const int mxn=30,mxe=1e3+10;
int n,tot=0,ans=-1;
int head[mxn],c[mxn];
struct ty{
    int to,next;
}edge[mxe<<1];
void add(int u,int v){
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void init(){
    tot=0;ans=-1;
    for(int i=0;i<=n;i++){
        head[i]=-1;
        c[i]=0;
    }
}
bool check(int u){
    for(int i=head[u];~i;i=edge[i].next){
        if(c[edge[i].to]==c[u]) return false;
    }
    return true;
}
bool dfs(int dep){
    if(dep>n) return true;
    for(int i=1;i<=26;i++){
        c[dep]=i;
        if(check(dep)){
            if(dfs(dep+1)) return true;
        }
        c[dep]=0;
    }
    return false;
}
int main(){
    while(scanf("%d",&n)==1&&n){
        init();
        getchar();
        for(int i=1;i<=n;i++){
            getchar();getchar();
            char ch;
            while(ch=getchar()){
                if(ch=='\n') break;
                add(i,ch-'A'+1);
            }
        }
        dfs(1);
        for(int i=1;i<=n;i++) ans=max(ans,c[i]);
        if(ans==1) printf("%d channel needed.\n",ans);
        else printf("%d channels needed.\n",ans);
    }
    return 0;
}

总结：

1.在搜索之前，先想好我们需要构造的状态图，想好状态图之后再去写代码会好想很多

2.一个方案作为一个状态图的顶点很常见