Untitled

a guest
Jul 27th, 2011
413
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <vector>
2. #include <cstdio>
3.
4. using namespace std;
5.
6. #define trav(x, y, z) for(typeof(x) z = x; z != y; z++)
7.
8. int bestSolution = 10000000;
9. int k;
10.
11. typedef pair<int, int> path; //weight, distance
12.
13. vector< vector<path > > adj;
14.
15. void combine(vector<path> *result, vector<path> *left, vector<path> *right){
16.   size_t li = 0;
17.   int ri = right->size()-1;
18.
19.   while(li != left->size() && ri != -1){
20.     int weight = (*left)[li].first + (*right)[ri].first;
21.     if(weight == k){
22.       int length = (*left)[li].second + (*right)[ri].second;
23.       if(length < bestSolution){
24.     bestSolution = length;
25.       }
26.       li++;
27.     } else if(weight < k){
28.       li++;
29.     } else {
30.       ri--;
31.     }
32.   }
33.   li = 0;
34.   ri = 0;
35.   for(size_t i = 0; i<left->size()+right->size(); i++){
36.     if(li == left->size() || (ri != right->size() && (*right)[ri].first < (*left)[li].first)){
37.       result->push_back((*right)[ri++]);
38.     } else if(ri == right->size() || (li != left->size() && (*left)[li].first < (*right)[ri].first)){
39.       result->push_back((*left)[li++]);
40.     } else {
41.       if((*right)[ri].second < (*left)[li].second){
42.     result->push_back((*right)[ri++]);
43.       } else {
44.     result->push_back((*left)[li++]);
45.       }
46.     }
47.   }
48. }
49.
50. vector<path> divide(vector<vector<path> > *paths, int a, int b){
51.   if(a == b) return (*paths)[a];
52.   //dela och merga
53.   vector<path> lower = divide(paths, a, (a+b)/2);
54.   vector<path> upper = divide(paths, (a+b)/2+1, b);
55.   vector<path> result;
56.   combine(&result, &lower, &upper);
57.   return result;
58. }
59.
60. void append(vector<path> *res, vector<path> *result, int dist){
61.   trav(result->begin(), result->end(), it){
62.     path prev = *it;
63.     res->push_back(path(prev.first+dist, prev.second+1));
64.   }
65. }
66.
67. vector<path> solve(int n, int from, int dist){
68.   vector< vector<path > > paths;
70.     path p = (*it);
71.     if(p.first == from) continue;
72.     paths.push_back(solve(p.first, n, p.second));
73.   }
74.   vector<path> single;
75.   single.push_back(path(0, 0));
76.   paths.push_back(single);
77.   int b = paths.size();
78.   if(b == 1){
79.     vector<path> result;
80.     append(&result, &paths[0], dist);
81.     return result;
82.   }
83.   vector<path> low = divide(&paths, 0, (b-1)/2);
84.   vector<path> high = divide(&paths, ((b-1)/2)+1, b-1);
85.   vector<path> result;
86.   combine(&result, &low, &high);
87.   vector<path> appended;
88.   append(&appended, &result, dist);
89.   return appended;
90. }
91.
92. int best_path(int n, int kk, int h[][2], int l[]){
93.   k = kk;
94.   bestSolution = 10000000;
97.   for(int i = 0; i < n-1; i++){
98.     int f = h[i][0];
99.     int t = h[i][1];
102.   }
103.   solve(0, -1, 0);
104.   if(bestSolution == 10000000) return -1;
105.   return bestSolution;
106. }
107.
108. void case1(){
109.   int n = 4;
110.   int k = 3;
111.   int h[][2] = {
112.     {0, 1},
113.     {1, 2},
114.     {1, 3}
115.   };
116.   int l[] = {1, 2, 4};
117.   printf("%d\n", best_path(n, k, h, l));
118. }
119.
120. void case2(){
121.   int n = 3;
122.   int k = 3;
123.   int h[][2] = {
124.     {0, 1},
125.     {1, 2}
126.   };
127.   int l[] = {1, 1};
128.   printf("%d\n", best_path(n, k, h, l));
129. }
130.
131. void case3(){
132.   int n = 11;
133.   int k = 12;
134.   int h[][2] = {
135.     {0, 1},
136.     {0, 2},
137.     {2, 3},
138.     {3, 4},
139.     {4, 5},
140.     {0, 6},
141.     {6, 7},
142.     {6, 8},
143.     {8, 9},
144.     {8, 10},
145.   };
146.   int l[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
147.   printf("%d\n", best_path(n, k, h, l));
148. }
149.
150. int main(){
151.   case1();
152.   case2();
153.   case3();
154. }