fork download
copy 
  1. #pragma comment(linker, ”/STACK:38777216“
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cassert>
  6. #include <cstdio>
  7. #include <stack>
  8. #include <string>
  9. #include <vector>
  10. #include <queue>
  11. #include <cmath>
  12. #include <time.h>
  13. #include <map>
  14. #include <set>
  15.  
  16. using namespace std;
  17.  
  18. const int N = 60005;
  19. const int inf = 1000 * 1000 * 1000;
  20. const int mod = 1000 * 1000 * 1000 + 7;
  21.  
  22. int n,m,k;
  23. queue <int> q;
  24. bool mark[N];
  25. vector < pair<int , int> > v[N];
  26. vector < pair<int , int> > g[N];
  27. vector < pair< int , pair<int,int> > > pp;
  28.  
  29. queue <int> pl;
  30.  
  31. int D[N];
  32. set < pair<int,int> > Q;
  33. set < pair<int,int> >::iterator it;
  34.  
  35. bool used[N];
  36. int gag , nn , mn;
  37. int order[N];
  38.  
  39. map <int,int> mp , mp1;
  40. int answ1 , answ2;
  41.  
  42. void dfs(int v,int p){
  43.     order[v] = 1;
  44.     nn++;
  45.     for(int i=0;i<(int)g[v].size();i++){
  46.         int to = g[v][i].first;
  47.         if(to == p || used[to])continue;
  48.         dfs(to , v);
  49.         order[v] += order[to];
  50.     }
  51. }
  52.  
  53. void dfs1(int v,int p){
  54.     int T = nn - order[v];
  55.     for(int i=0;i<(int)g[v].size();i++){
  56.         int to = g[v][i].first;
  57.         if(to == p || used[to])continue;
  58.         dfs1(to , v);
  59.         T = max(T , order[to]);
  60.     }
  61.     if(mn == -1 || T < mn){
  62.         mn = T;
  63.         gag = v;
  64.     }
  65. }
  66.  
  67. void made(int v,int p){
  68.     order[v] = 1;
  69.     for(int i=0;i<(int)g[v].size();i++){
  70.         int to = g[v][i].first;
  71.         if(to == p || used[to])continue;
  72.         made(to , v);
  73.         order[v] += order[to];
  74.     }
  75. }
  76.  
  77. int find_centroid(int v){
  78.     nn = 0;
  79.     dfs(v , -1);
  80.     mn = -1;
  81.     dfs1(v , -1);
  82.     made(gag , -1);
  83.     return gag;
  84. }
  85.  
  86. vector < pair<int,int> > P;
  87.  
  88. void solve(int v,int p,int r,int sum){
  89.     if(r > k)return ;
  90.     if(mp1[k - r] != 0){
  91.         if(sum + mp[k - r] > answ1){
  92.             answ1 = sum + mp[k - r];
  93.             answ2 = mp1[k - r];
  94.         }
  95.         else{
  96.             if(sum + mp[k - r] == answ1)
  97.                 answ2 += mp1[k - r];
  98.         }
  99.     }
  100.     if(p != -1) P.push_back(make_pair(r , sum));
  101.     for(int i=0;i<(int)g[v].size();i++){
  102.         int to = g[v][i].first;
  103.         int len = g[v][i].second;
  104.         if(used[to] || to == p)continue;
  105.         solve(to , v , r + 1 , sum + len);
  106.         if(p == -1){
  107.             for(int j=0;j<P.size();j++){
  108.                 int sz = P[j].first;
  109.                 int ss = P[j].second;
  110.                 if(ss > mp[sz]){
  111.                     mp[sz] = ss;
  112.                     mp1[sz] = 1;
  113.                 }
  114.                 else{
  115.                     if(ss == mp[sz])
  116.                         mp1[sz]++;
  117.                 }
  118.             }
  119.             P.clear();
  120.         }
  121.     }
  122. }
  123.  
  124. void centroid_decomposition(){
  125.     queue <int> Q;
  126.     Q.push(1);
  127.     while(!Q.empty()){
  128.         int v = Q.front();
  129.         Q.pop();
  130.         v = find_centroid(v);
  131.         mp.clear();
  132.         mp1.clear();
  133.         mp1[0] = 1;
  134.         solve(v , -1 , 0 , 0);
  135.         used[v] = true;
  136.         for(int i=0;i<(int)g[v].size();i++){
  137.             int to = g[v][i].first;
  138.             if(used[to])continue;
  139.             if(order[to] == 1)continue;
  140.             Q.push(to);
  141.         }
  142.     }
  143. }
  144.  
  145. void rec(int vv){
  146.     mark[vv] = true;
  147.     for(int i=0;i<(int)v[vv].size();i++){
  148.         int to = v[vv][i].second;
  149.         int len = v[vv][i].first;
  150.         if(mark[to])continue;
  151.         if(D[vv] + len == D[to]){
  152.             g[vv].push_back(make_pair(to , len));
  153.             g[to].push_back(make_pair(vv , len));
  154.             rec(to);
  155.         }
  156.     }
  157. }
  158.  
  159. int main(){
  160.     scanf("%d%d%d",&n,&m,&k);
  161.     for(int i=0;i<m;i++){
  162.         int aa,bb,cc;
  163.         scanf("%d%d%d" , &aa, &bb, &cc);
  164.         v[aa].push_back(make_pair(cc,bb));
  165.         v[bb].push_back(make_pair(cc,aa));
  166.     }
  167.     for(int i=1;i<=n;i++) D[i] = -1;
  168.     D[1] = 0;
  169.     Q.insert(make_pair(0 , 1));
  170.     while(!Q.empty()){
  171.         it = Q.begin();
  172.         int vv = (*it).second;
  173.         Q.erase(Q.begin());
  174.         for(int i=0;i<(int)v[vv].size();i++){
  175.             int to = v[vv][i].second;
  176.             int len = v[vv][i].first;
  177.             if(D[to] == -1 || D[vv] + len < D[to]){
  178.                 Q.erase(make_pair(D[to] , to));
  179.                 D[to] = D[vv] + len;
  180.                 Q.insert(make_pair(D[to] , to));
  181.             }
  182.         }
  183.     }
  184.     for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
  185.     rec(1);
  186.     k--;
  187.     centroid_decomposition();
  188.     cout<<answ1<<" "<<answ2<<endl;
  189.     return 0;
  190. }
  191. /*
  192. 10 9 4
  193. 1 2 1
  194. 1 3 2
  195. 1 4 4
  196. 3 5 3
  197. 3 6 3
  198. 5 7 5
  199. 4 8 2
  200. 4 9 3
  201. 9 10 4
  202. */
  203.  
Success #stdin #stdout 0s 18640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/kzZmuP
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 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!