Advertisement
Guest User

Untitled

a guest
Mar 10th, 2017
448
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <map>
  6. #include <set>
  7. #include <functional>
  8. #include <limits>
  9. #include <queue>
  10. #include <iomanip>
  11. #include <deque>
  12. #include <stack>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <complex.h>
  16. #include <cstdio>
  17.  
  18. using namespace std;
  19.  
  20. long long dist[1001][1001];
  21. long long cost[1001][1001];
  22.  
  23. vector<int> g[1001];
  24.  
  25. void dfs(int v, int p, int f, long long c)
  26. {
  27.     dist[f][v] = dist[v][f] = c;
  28.  
  29.     for (int adj_v : g[v])
  30.         if (adj_v != p)
  31.             dfs(adj_v, v, f, c + cost[v][adj_v]);
  32. }
  33.  
  34. int main()
  35. {
  36.     ios::sync_with_stdio(false);
  37.     cin.tie(nullptr);
  38.     cout.tie(nullptr);
  39.  
  40.     int T;
  41.     cin >> T;
  42.  
  43.     for (int test_case = 1; test_case <= T; test_case++)
  44.     {
  45.         int n, k;
  46.         cin >> n >> k;
  47.  
  48.         for (int v = 1; v <= n; v++)
  49.             g[v].clear();
  50.  
  51.         for (int v = 2; v <= n; v++)
  52.         {
  53.             int parent, length;
  54.             cin >> parent >> length;
  55.  
  56.             cost[parent][v] = cost[v][parent] = length;
  57.             g[v].push_back(parent);
  58.             g[parent].push_back(v);
  59.         }
  60.  
  61.         for (int v = 1; v <= n; v++)
  62.             dfs(v, v, v, 0);
  63.  
  64.         int max_v = 2;
  65.         for (int v = 3; v <= n; v++)
  66.             if (dist[1][v] > dist[1][max_v])
  67.                 max_v = v;
  68.  
  69.         bool used[1001] = {};
  70.         int next[1001] = {};
  71.  
  72.         next[1] = max_v;
  73.         next[max_v] = 1;
  74.         used[max_v] = true;
  75.  
  76.         long long max_path_length = 2 * dist[1][max_v];
  77.  
  78.         for (int i = 2; i <= k; i++)
  79.         {
  80.             int best_v = -1;
  81.             int best_place = -1;
  82.             long long best_increase = -1;
  83.  
  84.             for (int v = 2; v <= n; v++)
  85.                 if (!used[v])
  86.                 {
  87.                     int v0 = 1;
  88.                     int v1 = next[v0];
  89.                     do
  90.                     {
  91.                         long long cur_dist = dist[v0][v1];
  92.                         long long new_dist = dist[v0][v] + dist[v][v1];
  93.                         long long increase = new_dist - cur_dist;
  94.  
  95.                         if (increase > best_increase)
  96.                         {
  97.                             best_increase = increase;
  98.                             best_v = v;
  99.                             best_place = v0;
  100.                         }
  101.  
  102.                         v0 = v1;
  103.                         v1 = next[v0];
  104.  
  105.                     } while (v0 != 1);
  106.                 }
  107.  
  108.             used[best_v] = true;
  109.  
  110.             int tmp = next[best_place];
  111.             next[best_place] = best_v;
  112.             next[best_v] = tmp;
  113.  
  114.             max_path_length += best_increase;
  115.         }
  116.  
  117.         cout << "Case #" << test_case << ": " << max_path_length;
  118.         if (test_case < T)
  119.             cout << '\n';
  120.     }
  121. }
Advertisement
RAW Paste Data Copied
Advertisement