Super Phyllis（穷举+搜索）-白红宇

Super Phyllis（穷举+搜索）

阅读量：4952 次

发布时间：2019-06-12

本文共 2377 字，大约阅读时间需要 7 分钟。

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2723

题意：给出一些字符串u，v,代表u->v,问有几条边是多余的，也就是说去掉那些边后，u仍能到达v。

思路：穷举每条边，试着去掉该边，bfs搜索两个点是否仍然可达。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
           5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std; 10 char s1[210],s2[210],s[210][210]; 11 map
              
               f; 12 vector
               
                graph[210]; 13 int Map[210][210],vis[210]; 14 int n; 15 int cnt; 16 struct node 17 { 18 char s1[210]; 19 char s2[210]; 20 }edge[40010],tmp[40010]; 21 int cmp(const node a, const node b) 22 { 23 if(strcmp(a.s1,b.s1) == 0) 24 return strcmp(a.s2,b.s2)<0; 25 return strcmp(a.s1,b.s1)<0; 26 } 27 bool bfs(int s, int t) 28 { 29 queue
                
                  que; 30 while(!que.empty()) 31 que.pop(); 32 vis[s] = 1; 33 que.push(s); 34 while(!que.empty()) 35 { 36 int u = que.front(); 37 que.pop(); 38 if(u == t) 39 return true; 40 for(int i = 0; i < (int)graph[u].size(); i++) 41 { 42 int v = graph[u][i]; 43 if(!vis[v] && Map[u][v]) 44 { 45 que.push(v); 46 vis[v] = 1; 47 } 48 } 49 } 50 return false; 51 } 52 53 int main() 54 { 55 int item = 1; 56 while(cin >> n) 57 { 58 if(n == 0) break; 59 for(int i = 0; i <= 200; i++) 60 graph[i].clear(); 61 f.clear(); 62 memset(Map,0,sizeof(Map)); 63 cnt = 0; 64 for(int i = 0; i < n; i++) 65 { 66 cin>>s1>>s2; 67 if(!f[s1]) 68 { 69 f[s1] = ++cnt; 70 strcpy(s[cnt],s1); 71 } 72 if(!f[s2]) 73 { 74 f[s2] = ++cnt; 75 strcpy(s[cnt],s2); 76 } 77 graph[ f[s1] ].push_back( f[s2] ); 78 Map[ f[s1] ][ f[s2] ] = 1; 79 } 80 81 int res = 0; 82 for(int i = 1; i <= cnt; i++) 83 { 84 for(int j = 0; j < (int)graph[i].size(); j++) 85 { 86 int v = graph[i][j]; 87 memset(vis,0,sizeof(vis)); 88 Map[i][v] = 0; 89 if(bfs(i,v)) 90 { 91 strcpy(edge[res].s1,s[i]); 92 strcpy(edge[res].s2,s[v]); 93 res++; 94 } 95 else Map[i][v] = 1; 96 } 97 } 98 sort(edge,edge+res,cmp); 99 printf("Case %d: ",item++);100 int t = 0;101 if(res)102 tmp[t++] = edge[0];103 for(int i = 1; i < res; i++)104 {105 if(strcmp(edge[i].s1,edge[i-1].s1) == 0 && strcmp(edge[i].s2,edge[i-1].s2) == 0)106 continue;107 else108 {109 tmp[t++] = edge[i];110 }111 }112 printf("%d",t);113 for(int i = 0; i < t; i++)114 {115 printf(" %s,%s",tmp[i].s1,tmp[i].s2);116 }117 printf("\n");118 119 }120 return 0;121 }