额,我是直接dfs的思路,但是到case 5过不去了,感觉是太慢了。然后网上看题解,题目原型就是欧拉路径,
欧拉路径存在的条件是 要么点的度都是偶数,要么只有两个点的度是奇数。如果是两个点的度是奇数,起点和终点一定是这两个点,
然后我就加了一个判断,如果是有奇数度的点,取较小的点作为起点dfs。
dfs写的很丑,没组织好,还根据初始点判断,其实组织好没有这么麻烦...
但是到7还是过不去,继续看题解,发现有个大牛dfs同时加了个floodfill
其实我一直以为floodfill就是dfs和bfs...
然后我仿照加了个勉强过了
1 /* 2 3 ID: hubiao cave 4 5 PROG: fence 6 7 LANG: C++ 8 9 */ 10 11 12 13 14 #include<iostream> 15 16 #include<fstream> 17 #include<cstring> 18 #include<vector> 19 #include<deque> 20 #include<algorithm> 21 22 using namespace std; 23 24 25 26 vector<int> g_vertex_maps[501]; 27 deque<int> g_vertex_sequence; 28 int g_visit[501][501]; 29 int g_fence_number; 30 int g_max_vertex,g_min_vertex=1; 31 int g_count; 32 int node_counter[501]; 33 bool g_isover=false; 34 int special_start_vertex=8888; 35 36 void dfs(int); 37 bool floodfill(long node); 38 ofstream fout("fence.out"); 39 int main() 40 41 { 42 43 ifstream fin("fence.in"); 44 45 //ofstream fout("fence.out"); 46 47 fin>>g_fence_number; 48 49 int a,b; 50 for(int i=0;i<g_fence_number;i++) 51 { 52 fin>>a>>b; 53 if(i==0) 54 g_min_vertex=min(a,b); 55 56 g_vertex_maps[a].push_back(b); 57 g_vertex_maps[b].push_back(a); 58 59 node_counter[a]++; 60 node_counter[b]++; 61 g_visit[a][b]++; 62 g_visit[b][a]++; 63 64 g_max_vertex=g_max_vertex>max(a,b)?g_max_vertex:max(a,b); 65 g_min_vertex=g_min_vertex<min(a,b)?g_min_vertex:min(a,b); 66 67 } 68 69 for(int i=g_min_vertex;i<=g_max_vertex;i++) 70 { 71 if(!g_vertex_maps[i].empty()) 72 sort(g_vertex_maps[i].begin(),g_vertex_maps[i].end()); 73 74 if(g_vertex_maps[i].size()%2==1)//欧拉路径 找度为奇数的点为起点加速 75 special_start_vertex=min(special_start_vertex,i); 76 77 } 78 79 80 if(special_start_vertex==8888) 81 dfs(0); 82 else 83 dfs(special_start_vertex); 84 85 86 return 0; 87 88 89 } 90 91 void dfs(int start_vertex) 92 { 93 94 if(g_count==g_fence_number) 95 { 96 if(special_start_vertex!=8888) 97 g_vertex_sequence.push_front(special_start_vertex); 98 for(int i=0;i<g_vertex_sequence.size();i++) 99 fout<<g_vertex_sequence[i]<<endl; 100 g_isover=true; 101 exit(0); 102 //return; 103 } 104 105 if(start_vertex!=0&&!floodfill(start_vertex)) 106 { 107 return; 108 } 109 110 if(start_vertex==0) 111 { 112 for(int i=g_min_vertex;i<=g_max_vertex;i++) 113 { 114 115 for(int j=0;j<g_vertex_maps[i].size();j++) 116 { 117 g_count++; 118 g_visit[i][g_vertex_maps[i][j]]--; 119 g_visit[g_vertex_maps[i][j]][i]--; 120 g_vertex_sequence.push_back(i); 121 g_vertex_sequence.push_back(g_vertex_maps[i][j]); 122 node_counter[i]--; 123 node_counter[g_vertex_maps[i][j]]--; 124 125 dfs(g_vertex_maps[i][j]); 126 127 if(g_isover) 128 return; 129 130 node_counter[i]++; 131 node_counter[g_vertex_maps[i][j]]++; 132 133 g_vertex_sequence.pop_back(); 134 g_vertex_sequence.pop_back(); 135 g_visit[i][g_vertex_maps[i][j]]++; 136 g_visit[g_vertex_maps[i][j]][i]++; 137 138 g_count--; 139 } 140 } 141 } 142 else 143 { 144 for(int i=0;i<g_vertex_maps[start_vertex].size();i++) 145 { 146 int end_vertex=g_vertex_maps[start_vertex][i]; 147 if(g_visit[start_vertex][end_vertex]>0) 148 { 149 g_count++; 150 g_visit[start_vertex][end_vertex]--; 151 g_visit[end_vertex][start_vertex]--; 152 g_vertex_sequence.push_back(end_vertex); 153 154 node_counter[start_vertex]--; 155 node_counter[end_vertex]--; 156 157 dfs(end_vertex); 158 if(g_isover) 159 return; 160 161 node_counter[start_vertex]++; 162 node_counter[end_vertex]++; 163 164 g_count--; 165 g_visit[start_vertex][end_vertex]++; 166 g_visit[end_vertex][start_vertex]++; 167 g_vertex_sequence.pop_back(); 168 } 169 170 } 171 } 172 } 173 174 bool floodfill(long node) 175 { 176 int *stack=new int[501],top=-1; 177 bool vis[501]; 178 //for(int i=0;i<=500;i++) 179 memset(vis,0,sizeof(vis)); 180 181 stack[++top]=node; 182 vis[node]=true; 183 while(top>-1) 184 { 185 int m=stack[top--]; 186 for(int i=g_min_vertex;i<=g_max_vertex;i++) 187 { 188 if(g_visit[m][i]&&!vis[i]) 189 { 190 stack[++top]=i; 191 vis[i]=true; 192 } 193 } 194 } 195 196 for(int i=g_min_vertex;i<=g_max_vertex;i++) 197 { 198 if(!vis[i]&&node_counter[i]) 199 { 200 delete stack; 201 return false; 202 } 203 } 204 delete stack; 205 return true; 206 207 }