http://www.cppblog.com/Files/20024804/PowerOutage.zip
1 // BEGIN CUT HERE
2
3 // END CUT HERE
4
5 #include <iostream>
6 #include <string>
7 #include <vector>
8 #include <sstream>
9 #include <utility>
10 #include <algorithm>
11 #include <list>
12 #include <map>
13 #include <set>
14 #include <queue>
15 #include <stack>
16 #include <bitset>
17 #include <memory>
18 #include <cstdio>
19 #include <cmath>
20 #include <cstdlib>
21 #include <cctype>
22 #include <cstring>
23 #include <climits>
24
25 #define foreach(it, c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
26 #define forx(i, start, end, step) for(size_t i = (start); i != (end); i += (step))
27 #define fori(i, start, end) for(size_t i = (start); i != (end); i++)
28 #define forn(i, end) fori((i), 0, (end))
29 #define repeat(n) for(int i = 0; i < n; i++)
30
31 using namespace std;
32
33
34 class PowerOutage
35 {
36 public:
37 int estimateTimeOut(vector <int> fromJunction, vector <int> toJunction, vector <int> ductLength)
38 {
39 map<int, map<int, int> >G;
40 size_t num = 0;
41 for (size_t i = 0; i < fromJunction.size(); i++)
42 {
43 if (num < toJunction[i])
44 {
45 num = toJunction[i];
46 }
47 G[fromJunction[i]][toJunction[i]] = ductLength[i];
48 G[toJunction[i]][fromJunction[i]] = ductLength[i];
49 }
50 vector<int> visited;
51 repeat(num)
52 visited.push_back(false);
53
54 floyd(G, num + 1);
55 return dfs(G, visited, 0).first;
56 }
57
58 private:
59 vector<vector<int> > D;
60
61 vector<vector<int> > floyd(map<int, map<int, int> >G, int n)
62 {
63 repeat(n)
64 {
65 D.push_back(vector<int>(n));
66 }
67 forn(i, n)
68 forn(j, n)
69 D[i][j] = G[i][j];
70
71 forn(k, n)
72 forn(i, n)
73 forn(j, n)
74 {
75 if (i !=j && D[i][k] && D[k][j])
76 {
77 if (D[i][j])
78 D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
79 else
80 D[i][j] = D[i][k] + D[k][j];
81 }
82 }
83 return D;
84 }
85
86
87
88 pair<int, int> dfs(map<int, map<int, int> > &G, vector<int> &visited, int start)
89 {
90 // clog << "start: " << start << ",\tvistied[5]: " << visited[5] << endl;
91
92 int rlen = INT_MAX, rstop = start;
93 visited[start] = 1;
94
95 map<int, map<int, int> > G2 = G;
96 G2.erase(start);
97 foreach(i, G2)
98 foreach(j, i->second)
99 {
100 if (j->first == start)
101 i->second.erase(j);
102 }
103
104 vector<int> rv = visited;
105 map<int, map<int, int> > rG = G2;
106 bool enter = false;
107
108 foreach(it, G[start])
109 {
110 if (!visited[it->first])
111 {
112 int len = 0, stop = start;
113 vector<int> v2(visited.size()) ;
114 clog << "outter0:\tv2.size(): " << v2.size() << ", visited.size(): " << visited.size()
115 << "\tv2[5]: " << v2[5] << ",\tvistied[5]: " << visited[5] << endl;
116 copy(visited.begin(), visited.end(), v2.begin());
117 // forn(i, visited.size())
118 // v2.push_back(visited[i]);
119 clog << "outter1:\tv2.size(): " << v2.size() << ", visited.size(): " << visited.size()
120 << "\tv2[5]: " << v2[5] << ",\tvistied[5]: " << visited[5] << endl;
121 map<int, map<int, int> > G3 = G2;
122 foreach(jt, G[start])
123 {
124 if (!visited[jt->first])
125 {
126 enter = true;
127 pair<int, int> l = dfs(G3, v2, jt->first);
128 // clog << "inner:\tv2[5]: " << v2[5] << ",\tvistied[5]: " << visited[5] << endl;
129 len += jt->second + l.first + D[l.second][start];
130 if (D[stop][start] < D[l.second][start])
131 {
132 stop = l.second;
133 }
134 }
135 }
136 len -= D[stop][start];
137 if (len < rlen)
138 {
139 rlen = len;
140 rv = v2;
141 rG = G3;
142 rstop = stop;
143 }
144 }
145 }
146
147 G = rG;
148 visited = rv;
149 rlen = enter ? rlen : 0;
150 return make_pair(rlen, rstop);
151 }
152
153 // BEGIN CUT HERE
154 public:
155 void run_test(int Case)
156 {
157 if ((Case == -1) || (Case == 0)) test_case_0();
158 if ((Case == -1) || (Case == 1)) test_case_1();
159 if ((Case == -1) || (Case == 2)) test_case_2();
160 if ((Case == -1) || (Case == 3)) test_case_3();
161 if ((Case == -1) || (Case == 4)) test_case_4();
162 }
163 private:
164 template <typename T> string print_array(const vector<T> &V)
165 {
166 ostringstream os;
167 os << "{ ";
168 for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\",";
169 os << " }";
170 return os.str();
171 }
172 void verify_case(int Case, const int &Expected, const int &Received)
173 {
174 cerr << "Test Case #" << Case << "
";
175 if (Expected == Received) cerr << "PASSED" << endl;
176 else
177 {
178 cerr << "FAILED" << endl;
179 cerr << "\tExpected: \"" << Expected << '\"' << endl;
180 cerr << "\tReceived: \"" << Received << '\"' << endl;
181 }
182 }
183 void test_case_0()
184 {
185 int Arr0[] = {0};
186 vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
187 int Arr1[] = {1};
188 vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
189 int Arr2[] = {10};
190 vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0])));
191 int Arg3 = 10;
192 verify_case(0, Arg3, estimateTimeOut(Arg0, Arg1, Arg2));
193 }
194 void test_case_1()
195 {
196 int Arr0[] = {0,1,0};
197 vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
198 int Arr1[] = {1,2,3};
199 vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
200 int Arr2[] = {10,10,10};
201 vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0])));
202 int Arg3 = 40;
203 verify_case(1, Arg3, estimateTimeOut(Arg0, Arg1, Arg2));
204 }
205 void test_case_2()
206 {
207 int Arr0[] = {0,0,0,1,4};
208 vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
209 int Arr1[] = {1,3,4,2,5};
210 vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
211 int Arr2[] = {10,10,100,10,5};
212 vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0])));
213 int Arg3 = 165;
214 verify_case(2, Arg3, estimateTimeOut(Arg0, Arg1, Arg2));
215 }
216 void test_case_3()
217 {
218 int Arr0[] = {0,0,0,1,4,4,6,7,7,7,20};
219 vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
220 int Arr1[] = {1,3,4,2,5,6,7,20,9,10,31};
221 vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
222 int Arr2[] = {10,10,100,10,5,1,1,100,1,1,5};
223 vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0])));
224 int Arg3 = 281;
225 verify_case(3, Arg3, estimateTimeOut(Arg0, Arg1, Arg2));
226 }
227 void test_case_4()
228 {
229 int Arr0[] = {0,0,0,0,0};
230 vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
231 int Arr1[] = {1,2,3,4,5};
232 vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
233 int Arr2[] = {100,200,300,400,500};
234 vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0])));
235 int Arg3 = 2500;
236 verify_case(4, Arg3, estimateTimeOut(Arg0, Arg1, Arg2));
237 }
238
239 // END CUT HERE
240
241 };
242
243 // BEGIN CUT HERE
244 int main()
245 {
246 PowerOutage ___test;
247 ___test.run_test(2);
248 }
249 // END CUT HERE
250
116行copy后v2和visited的内容竟然不同!!!
把116行换成
v2 = visited;
也出错
247行换成
___test.run_test(-1);
出现栈错误
我的编译器是gcc 4.2
os是ubuntu 8.04, 32位
问题找到了，copy内容不同的原因是下标越界___test.run_test(-1)出错的原因是每次测试应该构造新对象来着。。。嗨，真是打扰各位看客了