本文共 2282 字，大约阅读时间需要 7 分钟。
题意：给你一个可能不联通的图，其中有k个点有计时器，计时器只能记录第一次到的时间，最后有L个计时器返回时间。
解题思路：深搜，按顺序找，每次找到不是site + 1 的电且有计时器的点就结束并把这个点加入我们的搜索池里面，每次搜完以后再看site + 1 是不是在池子里面，如果使得额话又从这个点开始搜索
解题代码：
1 // File Name: c.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月07日 星期日 13时56分37秒 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #define LL long long 25 #define maxn 100005 26 using namespace std; 27 28 int n , m , kn ,ln; 29 vector mp[maxn]; 30 int visit[maxn]; 31 int k[maxn]; 32 int l[maxn]; 33 int hs[maxn]; 34 int ok ; 35 int site; 36 int sum ; 37 void dfs(int s ) 38 { 39 int num = mp[s].size(); 40 for(int i = 0;i < num;i ++) 41 { 42 if(!visit[mp[s][i]]) 43 { 44 if(!k[mp[s][i]]){ 45 visit[mp[s][i]] = 1; 46 sum ++ ; 47 dfs(mp[s][i]); 48 } 49 else{ 50 if(l[mp[s][i]] == site + 1 ) 51 { 52 visit[mp[s][i]] = 1; 53 site ++ ; 54 sum ++ ; 55 dfs(mp[s][i]); 56 }else if(l[mp[s][i]]){ 57 hs[l[mp[s][i]]] = mp[s][i]; 58 } 59 } 60 } 61 } 62 if(site == ln) 63 { 64 ok = 1; 65 return ; 66 }else{ 67 if(hs[site + 1]) 68 { 69 visit[hs[site+1]] = 1; 70 site ++ ; 71 sum ++ ; 72 dfs(hs[site]); 73 } 74 } 75 } 76 int main(){ 77 int t; 78 scanf("%d",&t); 79 while(t--) 80 { 81 scanf("%d %d %d",&n,&m,&kn); 82 int a, b ; 83 for(int i = 1;i <= n;i ++) 84 mp[i].clear(); 85 memset(hs,0,sizeof(hs)); 86 memset(k,0,sizeof(k)); 87 memset(l,0,sizeof(l)); 88 memset(visit,0,sizeof(visit)); 89 int temp ; 90 for(int i = 1;i <= kn ;i ++ ) 91 { 92 scanf("%d",&temp); 93 k[temp] = 1 ; 94 } 95 for(int i = 1 ;i <= m;i ++) 96 { 97 scanf("%d %d",&a,&b); 98 mp[a].push_back(b); 99 mp[b].push_back(a);100 }101 int be;102 scanf("%d",&ln);103 for(int i = 1;i <= ln ;i ++)104 {105 scanf("%d",&temp);106 if(i == 1 )107 be = temp; 108 l[temp] = i;109 }110 if(ln < kn)111 {112 printf("No\n");113 continue;114 }115 ok = 0 ; 116 site = 1; 117 sum = 1 ; 118 visit[be] = 1;119 dfs(be); 120 121 if(ok && sum == n)122 printf("Yes\n");123 else printf("No\n");124 }125 return 0;126 }
转载于:https://www.cnblogs.com/zyue/p/3961448.html
