[POI2010]GIL-Guilds

摘要

之前文化课要准备月考,颓了一会儿 Hexo 博客配置,现在考完了,刷点水题恢复一下

给一张无向图,要求你用黑白灰给点染色,且满足对于任意一个黑点,至少有一个白点和他相邻;对于任意一个白点,至少有一个黑点与他相邻,对于任意一个灰点,至少同时有一个黑点和白点和灰点与他相邻,问能否成功

翻译过来,其实这是一道比较智障的题,直接构造答案. 对该图的生成树直接交替染色即可. 最后要判断是否有孤立点.

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+5,N=2e5+5;
int n,m;

struct qxx{int nex,t;};
qxx e[M*2];
int h[N],cnt=1;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}
int c[N],iscon[N];
void dfs(int u,int col){c[u]=col+1;
    for(int i=h[u];i;i=e[i].nex){const int v=e[i].t;
        if(c[v])continue;
        dfs(v,!col);
    }
}
int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add_path(u,v),add_path(v,u);
        iscon[u]=iscon[v]=1;
    }
    for(int i=1;i<=n;i++)if(!iscon[i])return puts("NIE"),0;
    for(int i=1;i<=n;i++)if(!c[i])dfs(i,1);
    puts("TAK");
    for(int i=1;i<=n;i++)puts(c[i]==1?"K":"S");
    return 0;
}

  转载请注明: Sshwy's Blog [POI2010]GIL-Guilds

 上一篇
[POI2010]PIL-Pilots [POI2010]PIL-Pilots
摘要 近期以 POI 的题为主,因为小清新~ 题意:给定 n,k 和一个长度为 n 的序列,求最长的最大值最小值相差不超过 k 的子串 最大最小就是单调队列啦,又因为是找连续子串的最大长度,显然就是尺取法的思路,每次纳入一个新的元素时更新
2019.04.02
下一篇 
NexT 文章随机背景图 NexT 文章随机背景图
摘要 NexT 主题做为 Hexo 博客中相当受欢迎的主题之一,得益于它简洁精致的外观,丰富多样的设置。不过相比与动态博客而言仍然少了许多重量级的功能。之前笔者介绍了 Hexo 文章加密的配置方法,今天作者来介绍 Hexo 博客随机背景头图
2019.03.30
  目录