fork download
  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. void print_best_path(int next[1000])
  22. {
  23. int v0 = 1;
  24. int v1 = next[v0];
  25. do
  26. {
  27. cout << v0 << " -> ";
  28.  
  29. v0 = v1;
  30. v1 = next[v0];
  31.  
  32. } while (v0 != 1);
  33.  
  34. cout << "1\n";
  35. }
  36.  
  37. int main()
  38. {
  39. int T;
  40. cin >> T;
  41.  
  42. for (int test_case = 1; test_case <= T; test_case++)
  43. {
  44. int n, k;
  45. cin >> n >> k;
  46.  
  47. for (int v = 1; v <= n; v++)
  48. g[v].clear();
  49.  
  50. for (int v = 2; v <= n; v++)
  51. {
  52. int parent, length;
  53. cin >> parent >> length;
  54.  
  55. cost[parent][v] = cost[v][parent] = length;
  56. g[v].push_back(parent);
  57. g[parent].push_back(v);
  58. }
  59.  
  60. for (int v = 1; v <= n; v++)
  61. dfs(v, v, v, 0);
  62.  
  63. int max_v = 2;
  64. for (int v = 3; v <= n; v++)
  65. if (dist[1][v] > dist[1][max_v])
  66. max_v = v;
  67.  
  68. bool used[1001] = {};
  69. int next[1001] = {};
  70.  
  71. next[1] = max_v;
  72. next[max_v] = 1;
  73. used[max_v] = true;
  74.  
  75. long long max_path_length = 2 * dist[1][max_v];
  76.  
  77. cout << "max_v=" << max_v << endl;
  78. cout << "max_path_length=" << max_path_length << endl;
  79. print_best_path(next);
  80.  
  81. for (int i = 2; i <= k; i++)
  82. {
  83. int best_v = -1;
  84. int best_place = -1;
  85. long long best_increase = -1;
  86.  
  87. for (int v = 2; v <= n; v++)
  88. if (!used[v])
  89. {
  90. int v0 = 1;
  91. int v1 = next[v0];
  92. do
  93. {
  94. long long cur_dist = dist[v0][v1];
  95. long long new_dist = dist[v0][v] + dist[v][v1];
  96. long long increase = new_dist - cur_dist;
  97.  
  98. if (increase > best_increase)
  99. {
  100. best_increase = increase;
  101. best_v = v;
  102. best_place = v0;
  103. }
  104.  
  105. v0 = v1;
  106. v1 = next[v0];
  107.  
  108. } while (v0 != 1);
  109. }
  110.  
  111. used[best_v] = true;
  112.  
  113. int tmp = next[best_place];
  114. next[best_place] = best_v;
  115. next[best_v] = tmp;
  116.  
  117. max_path_length += best_increase;
  118.  
  119. cout << "best_v=" << best_v << " best_increase=" << best_increase <<
  120. " max_path_length=" << max_path_length << endl;
  121. print_best_path(next);
  122. }
  123.  
  124. cout << "Case #" << test_case << ": " << max_path_length;
  125. if (test_case < T)
  126. cout << '\n';
  127. }
  128. }
Success #stdin #stdout 0s 30920KB
stdin
1
5 3
1 10
2 20
2 20
1 20
stdout
max_v=3
max_path_length=60
1 -> 3 -> 1
best_v=4 best_increase=40 max_path_length=100
1 -> 4 -> 3 -> 1
best_v=5 best_increase=60 max_path_length=160
1 -> 4 -> 5 -> 3 -> 1
Case #1: 160