The 2014 ACM-ICPC Asia Mudanjiang Regional First Round C

题意：

这个是The 2014 ACM-ICPC Asia Mudanjiang Regional First Round 的C题，这个题目当时自己想的很复杂，想的是优先队列广搜，然后再在前向星里排序，结果写了好长，然后wa掉了，还好后来被队友A了，题意是给你一个无向图，然后让你遍历所有的点，但是有一些点的之间的遍历顺序有限制，最后问你能否遍历所有点。

思路：

今早起来才用自己的思路A了这个题，其实我们可以按照限制的顺序，一个一个枚举，对于当前的这个点，我们从它开始搜，见到限制的点就continue，其他的就继续遍历，只要当前的这个点能找到一个之前限制点搜的时候遍历过的点就行（除了第一个点），就这样遍历到最后，然后看看是否所有的点都被mark了就行了，具体看代码吧。

#include<stdio.h>

#include<string.h>

#include<queue>

#define N_node 110000

#define N_edge 440000

using namespace std;

typedef struct

{

   int to ,next;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int mk_cgq[N_node] ,mark[N_node] ,mk[N_node];

int cgq[N_node];

int ok;

queue<int>q;

void add(int a ,int b)

{

   E[++tot].to = b;

   E[tot].next = list[a];

   list[a] = tot;

}

void DFS(int s)

{

   for(int k = list[s] ;k ;k = E[k].next)

   {

      int to = E[k].to;

      if(mark[to]) ok = 1;

      if(mk[to] || mk_cgq[to]) continue;

      mk[to] = 1;

      q.push(to);

      DFS(to);

   }

}

int main ()

{

   int n ,m ,l ,t ,a ,b ,i ,k;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d %d %d" ,&n ,&m ,&k);

      for(i = 1 ;i <= k ;i ++)

      scanf("%d" ,&a);

      memset(list ,0 ,sizeof(list)) ,tot = 1;

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d %d" ,&a ,&b);

         add(a ,b) ,add(b ,a);

      }

      scanf("%d" ,&l);

      memset(mk_cgq ,0 ,sizeof(mk_cgq));

      for(i = 1 ;i <= l ;i ++)

      {

         scanf("%d" ,&cgq[i]);

         mk_cgq[cgq[i]] = 1;

      }

      if(l != k)

      {

         printf("No\n");

         continue;

      }

      memset(mark ,0 ,sizeof(mark));

      memset(mk ,0 ,sizeof(mk));

      for(i = 1 ;i <= k ;i ++)

      {

         mk[cgq[i]] = 1;

         ok = 0;

         while(!q.empty())q.pop();

         DFS(cgq[i]);

         while(!q.empty())

         {

            mark[q.front()] = 1;

            q.pop();

         }

         mark[cgq[i]] = 1;

         if(!ok && i != 1) break;

      }

      if(i != k + 1)

      {

         printf("No\n");

         continue;

      }

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

      if(!mark[i]) break;

      if(i != n + 1) printf("No\n");

      else printf("Yes\n");

   }

   return 0;

}

巴特西

The 2014 ACM-ICPC Asia Mudanjiang Regional First Round C

最新文章

热门文章