fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(3e5)+7;
  14.  
  15. int n , m , k , sz[maxN];
  16. vector<int> p[maxN];
  17. bool del[maxN];
  18. ll res_dist = 0;
  19. vector<ii> g[maxN] , res_pair;
  20.  
  21. void dfs_size(int u , int par){
  22.     sz[u] = sz(p[u]);
  23.     for (auto e : g[u]){
  24.         int v = e.fi;
  25.         if (v != par){
  26.             dfs_size(v , u);
  27.             sz[u] += sz[v];
  28.         }
  29.     }
  30. }
  31.  
  32. int dfs_find(int u , int par , int half){
  33.     for (auto e : g[u]){
  34.         int v = e.fi;
  35.         if (v != par && sz[v] > half){
  36.             return dfs_find(v , u , half);
  37.         }
  38.     }
  39.     return u;
  40. }
  41.  
  42. int cnt = 0;
  43. vector<int> ver , tmp[maxN];
  44.  
  45. void dfs_ins(int u , int par , ll d){
  46.     res_dist += 1ll * sz(p[u]) * d;
  47.     for (int x : p[u]) tmp[cnt].push_back(x);
  48.     for (auto e : g[u]){
  49.         int v = e.fi;
  50.         int w = e.se;
  51.         if (v != par){
  52.             dfs_ins(v , u , d + 1ll * w);
  53.         }
  54.     }
  55. }
  56.  
  57. void prepare(){
  58.     dfs_size(1 , 0);
  59.     int u = dfs_find(1 , 0 , k / 2);
  60.     for (auto e : g[u]){
  61.         int v = e.fi;
  62.         int w = e.se;
  63.         cnt++;
  64.         dfs_ins(v , u , 1ll * w);
  65.     }
  66.     cnt++;
  67.     for (int x : p[u]) tmp[cnt].push_back(x);
  68.     priority_queue<ii> pq;
  69.     for (int i = 1 ; i <= cnt ; i++){
  70.         if (tmp[i].empty() == 0) pq.push({sz(tmp[i]) , i});
  71.     }
  72.     cout << res_dist << "\n";
  73.     while (sz(pq) > 1){
  74.         auto X = pq.top(); pq.pop(); int u = X.se;
  75.         auto Y = pq.top(); pq.pop(); int v = Y.se;
  76.         cout << tmp[u].back() << " " << tmp[v].back() << "\n";
  77.         tmp[u].pop_back();
  78.         tmp[v].pop_back();
  79.         if (tmp[u].empty() == 0) pq.push({sz(tmp[u]) , u});
  80.         if (tmp[v].empty() == 0) pq.push({sz(tmp[v]) , v});
  81.     }
  82.     if (pq.empty() == 0){
  83.         int u = pq.top().se;
  84.         for (int i = 0 ; i < sz(tmp[u]) ; i += 2){
  85.             cout << tmp[u][i] << " " << tmp[u][i + 1] << "\n";
  86.         }
  87.     }
  88. }
  89.  
  90. void solve(){
  91.     cin >> n >> m >> k;
  92.     for (int i = 1 ; i <= m ; i++){
  93.         int u , v , w;
  94.         cin >> u >> v >> w;
  95.         g[u].push_back({v , w});
  96.         g[v].push_back({u , w});
  97.     }
  98.     for (int i = 1 ; i <= k ; i++){
  99.         int x; cin >> x;
  100.         p[x].push_back(i);
  101.     }
  102.     prepare();
  103. }
  104.  
  105. #define name "partner"
  106.  
  107. int main(){
  108.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109.     if (fopen(name".INP" , "r")){
  110.         freopen(name".INP" , "r" , stdin);
  111.         freopen(name".OUT" , "w" , stdout);
  112.     }
  113.     int t = 1; cin >> t;
  114.     solve();
  115.     return 0;
  116. }
  117.  
  118.  
Success #stdin #stdout 0.01s 25060KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Eqdr5u
language:
C++ (gcc 8.3)
created:
7 days 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!