题解 P3496 【[POI2010]GIL-Guilds】

· · 题解

这道题标签是广搜，于是我就用深搜来做。

不要问我为什么快考CSP了还来发题解

思路

首先看题：白点或黑点都只需要旁边有一个另一种颜色的点就行了，而灰色不一样，它需要一白一黑。显然，灰色要求更多，也就更难处理，那么，就不涂它了吧。

一个点白点或黑点，只要有点与它相连，这两个点颜色相反，就可以满足。而如果一个点不与其他任何点连通，不管涂不涂灰色，都无法满足。也就是说，在任何情况，都可以不涂灰色。

世界一下子清静了许多：只有黑点和白点。那么，对于每一个连通图，都搜一遍，第一个点记为白点，后面每搜到一个点，都涂上与前一个点相反的颜色，如果涂过就不涂了。而如果有一个连通图只有一个点，那么一定不行，输出NIE就好了。

细节

有的细节还是有必要提一下。

在读入边的时候，把这个边两个端点都标记一下，这样只要有没标记到的点，一定是单独的，即无法完成。

建边时，要用邻接表优化空间，不然会超空间。

深搜时，一定要没有搜到（新的连通图）再继续搜，不然绝对超时。

技巧

这里的技巧就是如何把代码写的更简单（更短）

判断是否搜过

开一个整型的color数组，值为0表示未染色（未遍历），1表示白色，2表示黑色。

判断只需要color[i]==0

求相反颜色

求相反颜色方法：color[i]%2+1（1直接变2，2直接变1）。

代码

相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——

#include<cstdio>
using namespace std;
const int MAXN=200010,MAXM=1000010;//注意边数要乘2
int h[MAXN],color[MAXN],tot=0;//h为邻接表中的head，tot为总边数
bool vis[MAXN];//记录是否有连接
struct Edge{//边的结构体
    int v;
    int next;//next记录这条边在邻接表中指向同端点的另一条边
}e[MAXM];
void addEdge(int u,int v){//建边
    tot++;
    e[tot].v=v;
    e[tot].next=h[u],h[u]=tot;
}
void dfs(int u){//深搜，u为原节点，保证已染色
    for(int k=h[u];k;k=e[k].next){//邻接表查找
        int v=e[k].v;
        color[v]=color[u]%2+1;//公式
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--){
        int uu,vv;
        scanf("%d%d",&uu,&vv);
        vis[uu]=1,vis[vv]=1;//记录
        addEdge(uu,vv);addEdge(vv,uu);//建边
    }
    for(int i=1;i<=n;i++)//判断是否不行
        if(!vis[i]){
            printf("NIE\n");//输出
            return 0;//返回
        }
    printf("TAK\n");//直接输出
    for(int i=1;i<=n;i++)//每个点都搜一遍
        if(!color[i]){//没搜过
            color[i]=1;//先设为白点
            dfs(i);//开搜
        }
    for(int i=1;i<=n;i++){//输出
        if(color[i]==1) printf("K\n");
        else printf("S\n");
    }
    return 0;//华丽结束
}

在CSP前写一篇题解也不容易，别忘了点个赞！