Advertisement
Guest User

Untitled

a guest
Jul 27th, 2011
413
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.45 KB | None | 0 0
  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;
  69.   trav(adj[n].begin(), adj[n].end(), it){
  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;
  95.   adj.clear();
  96.   adj.resize(n);
  97.   for(int i = 0; i < n-1; i++){
  98.     int f = h[i][0];
  99.     int t = h[i][1];
  100.     adj[f].push_back(path(t, l[i]));
  101.     adj[t].push_back(path(f, l[i]));
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement