题意

给一张无向图，要求你用黑(\(K\))白(\(S\))灰(\(N\))给点染色，且满足对于任意一个黑点，至少有一个白点和他相邻；对于任意一个白点，至少有一个黑点与他相邻，对于任意一个灰点，至少同时有一个黑点和白点和灰点与他相邻，问能否成功。成功则输出TAK并输出每个点的颜色，否则输出一行NIE。

思路

这是一道结论题，看起来很不可做，但实际上只需要分析一下就会发现并不难。

对于一张有解的无向图，若不把点染成灰色也一定有解。
- 既然灰点需要旁边同时有白点和黑点，那么这个点既满足被染成白色的条件也满足被染成黑色的条件，而灰点对于染黑和染白没有任何贡献，我们把一种解中的灰点改为黑点或是白点也一定是一种解。
对于一张\(n\)个点的无向连通图\((n\geq 2)\)，其一定有解。
- 对于\(n=2\)，显然成立。那么对于\(n\geq 3\)，假设\(n-1\)个点时有解，那么再加入一个点，并把它和其他点相连，它的旁边一定会有一个被染色的点，无论黑白，那么它一定满足被染成黑色或白色，所以这样的图也有解，由数学归纳法，得证。
无解的情况有且仅有无向图中的最小联通块的大小为\(1\)。
- 由上一结论，当\(n\geq 2\)时一定有解，当\(n=1\)时它不满足被染成任何一种颜色，无解。得证。

所以，我们只需要将点染成任意颜色，将与这个点相连的所有点染成相反颜色，在染色过程中判断当前联通块大小，就能构造出一个解了。

AC代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN=2e5+5;

const int MAXM=1e6+5;

int n,m,col[MAXN];

int cnt,top[MAXN],to[MAXM],nex[MAXM];

char hjj[3]={'@','K','S'};

int read()

{

    int re=0;char ch=getchar();

    while(!isdigit(ch)) ch=getchar();

    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();

    return re;

}

int dfs(int now)

{

    int re=1;

    for(int i=top[now];i;i=nex[i])

    {

        if(col[to[i]]) continue;

        col[to[i]]=2/col[now];

        re+=dfs(to[i]);

    }

    return re;

}

int main()

{

    n=read(),m=read();

    while(m--)

    {

        int x=read(),y=read();

        to[++cnt]=y,nex[cnt]=top[x],top[x]=cnt;

        to[++cnt]=x,nex[cnt]=top[y],top[y]=cnt;

    }

    for(int i=1;i<=n;i++)

        if(!col[i])

        {

            col[i]=1;

            if(dfs(i)==1)

            {

                printf("NIE");

                return 0;

            }

        }

    puts("TAK");

    for(int i=1;i<=n;i++) printf("%c\n",hjj[col[i]]);

    return 0;

}

geq

Luogu P3496 [POI2010]GIL-Guilds(贪心+搜索)

题意

思路

AC代码