hdu 5469 Antonidas （dfs+剪枝）2015 ACM/ICPC Asia Regional Shanghai Online

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int N = 10010;
  8 
  9 struct Edge
 10 {
 11     int to, next;
 12 }edge[N<<1];
 13 
 14 int head[N], fm[N];
 15 int dis[N];
 16 bool vis[N];
 17 int n, t, k;
 18 int len;
 19 char s1[N], s2[N];
 20 
 21 void add(int u, int v)
 22 {
 23     edge[k].to = v;
 24     edge[k].next = head[u];
 25     head[u] = k++;
 26 }
 27 
 28 void tdfs(int x)
 29 {
 30     int mdis = -1;
 31     for(int i = head[x]; i != -1; i = edge[i].next)
 32     {
 33         int v = edge[i].to;
 34         if(!vis[v])
 35         {
 36             vis[v] = 1;
 37             tdfs(v);
 38             fm[v] = x;
 39             mdis = mdis > dis[v] ? mdis : dis[v];
 40         }
 41     }
 42     dis[x] = mdis == -1 ? 1 : mdis+1;
 43 }
 44 
 45 bool dfs(int x, int disx, int mlen)
 46 {
 47     if(disx-1 > len) return 1;
 48     if(dis[x] > mlen)
 49     {
 50         for(int i = head[x]; i != -1; i = edge[i].next)
 51         {
 52             int v = edge[i].to;
 53             if(!vis[v] && s1[v] == s2[disx])
 54             {
 55                 vis[v] = 1;
 56                 if(dfs(v, disx+1, mlen-1)) return 1;
 57             }
 58         }
 59     }
 60     else if(!vis[fm[x]] && s1[fm[x]] == s2[disx])
 61     {
 62         vis[fm[x]] = 1;
 63         return dfs(fm[x], disx+1, mlen-1);
 64     }
 65     return 0;
 66 }
 67 
 68 void init()
 69 {
 70     scanf("%d", &n);
 71     k = 0;
 72     memset(head, -1, sizeof(head));
 73     for(int i = 0; i < n; i++)
 74     {
 75         int a, b;
 76         scanf("%d%d", &a, &b);
 77         add(a, b);
 78         add(b, a);
 79     }
 80     memset(dis, 0, sizeof(dis));
 81     memset(vis, 0, sizeof(vis));
 82     tdfs(1);
 83     scanf("%s%s", s1+1, s2+1);
 84     len = strlen(s2+1)-1;
 85 }
 86 
 87 int main()
 88 {
 89     //freopen("test.in", "r", stdin);
 90     scanf("%d", &t);
 91     for(int tm = 1; tm <= t; tm++)
 92     {
 93         init();
 94         bool flag = 0;
 95         for(int i = 1; i <= n; i++)
 96         {
 97             if(s1[i] == s2[1])
 98             {
 99                 memset(vis, 0, sizeof(vis));
100                 if(dfs(i, 2, len))
101                 {
102                     flag = 1;
103                     break;
104                 }
105             }
106         }
107         printf("Case #%d: ", tm);
108         if(flag) printf("Find\n");
109         else printf("Impossible\n");
110     }
111 }