fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. long long dist[1001][1001];
  8. long long cost[1001][1001];
  9.  
  10. vector<int> g[1001];
  11.  
  12. void dfs(int v, int p, int f, long long c)
  13. {
  14.     dist[f][v] = dist[v][f] = c;
  15.  
  16.     for (int adj_v : g[v])
  17.         if (adj_v != p)
  18.             dfs(adj_v, v, f, c + cost[v][adj_v]);
  19. }
  20.  
  21. int main()
  22. {
  23.     int T;
  24.     cin >> T;
  25.  
  26.     for (int test_case = 1; test_case <= T; test_case++)
  27.     {
  28.         int n, k;
  29.         cin >> n >> k;
  30.  
  31.         for (int v = 1; v <= n; v++)
  32.             g[v].clear();
  33.  
  34.         for (int v = 2; v <= n; v++)
  35.         {
  36.             int parent, length;
  37.             cin >> parent >> length;
  38.  
  39.             cost[parent][v] = cost[v][parent] = length;
  40.             g[v].push_back(parent);
  41.             g[parent].push_back(v);
  42.         }
  43.  
  44.         for (int v = 1; v <= n; v++)
  45.             dfs(v, v, v, 0);
  46.  
  47.         int max_v = 2;
  48.         for (int v = 3; v <= n; v++)
  49.             if (dist[1][v] > dist[1][max_v])
  50.                 max_v = v;
  51.  
  52.         bool used[1001] = {};
  53.         int next[1001] = {};
  54.  
  55.         next[1] = max_v;
  56.         next[max_v] = 1;
  57.         used[max_v] = true;
  58.  
  59.         long long max_path_length = 2 * dist[1][max_v];
  60.  
  61.  		cout << "max_path_length=" << max_path_length << endl;
  62.  
  63.         for (int i = 2; i <= k; i++)
  64.         {
  65.             int best_v = -1;
  66.             int best_place = -1;
  67.             long long best_increase = -1;
  68.  
  69.             for (int v = 2; v <= n; v++)
  70.                 if (!used[v])
  71.                 {
  72.                     int v0 = 1;
  73.                     int v1 = next[v0];
  74.                     do
  75.                     {
  76.                         long long cur_dist = dist[v0][v1];
  77.                         long long new_dist = dist[v0][v] + dist[v][v1];
  78.                         long long increase = new_dist - cur_dist;
  79.  
  80.                         if (increase > best_increase)
  81.                         {
  82.                             best_increase = increase;
  83.                             best_v = v;
  84.                             best_place = v0;
  85.                         }
  86.  
  87.                         v0 = v1;
  88.                         v1 = next[v0];
  89.  
  90.                     } while (v0 != 1);
  91.                 }
  92.  
  93.             used[best_v] = true;
  94.  
  95.             int tmp = next[best_place];
  96.             next[best_place] = best_v;
  97.             next[best_v] = tmp;
  98.  
  99.             max_path_length += best_increase;
  100.  
  101.             cout << "best_v=" << best_v << " best_increase=" << best_increase <<
  102.             " max_path_length=" << max_path_length << endl;
  103.         }
  104.  
  105.         cout << "Case #" << test_case << ": " << max_path_length;
  106.         if (test_case < T)
  107.             cout << '\n';
  108.     }
  109. }
Success #stdin #stdout 0s 31744KB
comments (?)
stdin
copy 
1
5 3
1 10
2 20
2 20
1 20
stdout
copy 
max_path_length=60
best_v=4 best_increase=40 max_path_length=100
best_v=5 best_increase=60 max_path_length=160
Case #1: 160
https://ideone.com/q2NzDS
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!