P7428题解

· · 题解

1 思路

注：本题的解法正确性并未得到证明，但是能过。

我们一看题目，发现题目还有重点突出每个点最多和 7 个点相邻。那么，我们就可以知道，最复杂最可能无解的图，就是 8 个点的完全图。

然鹅，哪怕是这样，都有解，即样例。

所以我们可以得出结论：没有无解的情况。可能是因为 小 B 的孝心感天动地。

那么怎么构造呢？深搜是明显不行的。我们可以使用一种奇技淫巧。

首先，将颜色编号为 0-3，然后，找出所有不满足要求的点，加入队列。

每次从队首取一个点。如果这个点已经满足要求就不去动它，否则，将它的颜色改成所有与它直接相连的点的中最稀有的颜色。

依据容斥原理，我们可以证明，这个颜色在周围只有 1 个或者 0 个点拥有。

当然了，改完颜色后，又要判断所有与之相连的点有哪个或哪些不满足要求，压入队列。

队列为空时，答案就出来了。

2 代码与记录

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define max_n 25000//最大点数
#define max_m 200000//最大边数
int t;//测试数据组数
int n;//点数
int m;//边数
struct E{
    int v,nx;
}e[max_m+2];//边
int ei;//下标
int fir[max_n+2];//开始路径
int micnt,micol;//周围最少的颜色的数量与那个颜色
int col[max_n+2];//颜色
queue<int>q;//队列
inline void addedge(int u,int v){
    e[++ei]=(E){v,fir[u]}; fir[u]=ei;
}
int asksame(int u,int x){
    int res=0;
    for(int i=fir[u];i;i=e[i].nx){
        if(x==col[e[i].v])++res;
    }
    return res;//在点u周围有res个颜色为x的点
}
inline int mi(int a,int b){
    return a<b?a:b;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("P7428_1.in","r",stdin);
    freopen("P7428_1.out","w",stdout);
    #endif
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        ei=0;
        memset(fir,0,sizeof(fir));
        for(int i=1,u,v;i<=m;++i){
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        memset(col,0,sizeof(col));
        while(!q.empty())q.pop();
        for(int i=1;i<=n;++i){
            if(asksame(i,col[i])>1)q.push(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            if(asksame(u,col[u])<=1)continue;
            micnt=8;
            for(int i=0,k;i<4;++i){
                k=asksame(u,i);
                if(k<micnt){
                    micnt=k;
                    micol=i;
                }
            }
            col[u]=micol;//此时必定有micnt<=1
            for(int i=fir[u],v;i;i=e[i].nx){
                v=e[i].v;
                if(col[v]==micol&&asksame(v,micol)>1)q.push(v);
            }
        }
        for(int i=1;i<=n;++i)putchar(col[i]+'a');
        puts("");
    }
    return 0;
}

记录传送门

By dengziyue