20024804

常用链接

统计

最新评论

stl奇怪的copy问题[已解决]

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<intint> >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<intint> >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 !=&& 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<intint> dfs(map<int, map<intint> > &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<intint> > 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<intint> > 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<intint> > G3 = G2;
122                 foreach(jt, G[start])
123                 {
124                     if (!visited[jt->first])
125                     {
126                         enter = true;
127                         pair<intint> 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)出错的原因是每次测试应该构造新对象来着。。。
嗨,真是打扰各位看客了

posted on 2008-11-05 23:49 尘埃 阅读(1721) 评论(8)  编辑 收藏 引用

评论

# re: stl奇怪的copy问题 2008-11-06 10:01 尘埃

丢人死了

问题找到了,copy内容不同的原因是下标越界
___test.run_test(-1)出错的原因是每次测试应该构造新对象来着。。。
嗨,真是打扰各位看客了  回复  更多评论   

# re: stl奇怪的copy问题[已解决] 2008-11-06 11:42 abettor

真要命,就怕碰见上来就贴一大堆代码的。
有比这还可怕的吗?——有!贴一大堆代码还没注释!  回复  更多评论   

# re: stl奇怪的copy问题[已解决] 2008-11-06 11:58 尘埃

@abettor
呵呵,抱歉哦,主要是我觉得可能问题跟代码的意义没有关系。。。而且这种代码不是工业代码,只是练手的,就没有注释了,抱歉。。。  回复  更多评论   

# re: stl奇怪的copy问题[已解决] 2008-11-06 15:58 Wang Feng

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>


还有比这更可怕的么?19个头文件…………  回复  更多评论   

# re: stl奇怪的copy问题[已解决] 2008-11-06 16:00 尘埃

@Wang Feng
这仅仅是为了参加比赛,比赛的时候编码时间很重要,所以就没有注意这么多
真正做项目的时候我是不会这样写的  回复  更多评论   

# re: stl奇怪的copy问题[已解决] 2008-11-06 16:39 Wang Feng

不要当真,当我是纯粹灌水就好了:)  回复  更多评论   

# re: stl奇怪的copy问题[已解决] 2008-11-06 18:55 尘埃

@Wang Feng
:)  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理