【Codeforces 1019C】Sergey's problem

构造。

题目大意:

给定一张有向图,你需要选择一些结点染黑,其他点为白色,并满足条件:

  • 黑点之间没有边相连。
  • 对于一个白点,存在一个黑点,能在走不超过 22 条边后到达这个白点。

输出一种方案。

题解:

这是一种挺妙的构造方案。

我们定义一个点有一个状态为“被控制的”或者“不被控制的”。

我们按照某种顺序枚举所有点,如果它不是被控制的,则将它染黑,并将它 1 步内能到的点都标记为被控制的。

然后倒序枚举所有点,如果它是黑点,那么把和它相连的黑点变成白色。

剩下的黑点就是满足条件的方案。

为什么这样是对的呢?

考虑 uv,且 uv 都是黑点,那么 u 必然比 v 后染色,否则 v 不可能是黑点。那么在倒序访问的时候,u 一定先被访问到,v 就会被删除。而属于 v 管辖的只是走 1 条边能访问到的点,而 uv 也是一条边,即原来 v 控制的点,现在变成了 u 控制。那么仍然保证所有点都“被控制”。

再考虑 uvw,这里 u 肯定会被先访问,那么 v 就没有了,而 w 仍然存在。这样是没有问题的。更长的链也可依此类推。

于是时间复杂度 O(n+m)

Code:

  1. #include<cstdio>
  2. #include<bitset>
  3. using namespace std;
  4. const int N=1e6+5;
  5. struct edge{
  6. int to,nxt;
  7. }e[N];
  8. int head[N],cnt,n,m;
  9. bool vis[N];
  10. bitset<N>bt;
  11. inline void dfs(int u,int dep){
  12. vis[u]=1;
  13. if(dep==1)return;
  14. for(int i=head[u];i;i=e[i].nxt)if(!vis[e[i].to])dfs(e[i].to,dep+1);
  15. }
  16. int main(){
  17. scanf("%d%d",&n,&m);
  18. while(m--){
  19. int u,v;
  20. scanf("%d%d",&u,&v);
  21. e[++cnt]=(edge){v,head[u]},head[u]=cnt;
  22. }
  23. for(int i=1;i<=n;++i)if(!vis[i]){
  24. vis[i]=bt[i]=1;
  25. for(int j=head[i];j;j=e[j].nxt)vis[e[j].to]=1;
  26. }
  27. for(int i=n;i;--i)if(bt.test(i))for(int j=head[i];j;j=e[j].nxt)bt.reset(e[j].to);
  28. printf("%d\n",bt.count());
  29. for(int i=1;i<=n;++i)if(bt.test(i))printf("%d ",i);
  30. return 0;
  31. }

Gitalking ...