fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class Graph
  6. {
  7.     int V;
  8.     list<pair<int,int>> *l;
  9.  
  10. public:
  11.     Graph(int v)
  12.     {
  13.         V = v;
  14.         l = new list<pair<int,int>> [V+1];
  15.     }
  16.     void addEdge(int u, int v,int cost)
  17.     {
  18.         l[u].push_back(make_pair(v,cost));
  19.         l[v].push_back(make_pair(u,cost));
  20.     }
  21.  
  22.     int dfsHelper(int node,bool *visited, int *count, int &ans)
  23.     {
  24.         //mark the node as visited
  25.         visited[node] = true;
  26.         count[node] = 1;
  27.  
  28.         for (auto nbr_pair:l[node])
  29.         {
  30.             int nbr = nbr_pair.first;
  31.             int wt = nbr_pair.second;
  32.             if (!visited[nbr])
  33.             {
  34.                 // the count of node increases as we return from the children node
  35.                 count[node] += dfsHelper(nbr,visited,count,ans);
  36.  
  37.                 //That count helps us to find the number of nodes of that component
  38.                 int nx = count[nbr];
  39.                 int ny = V - nx;
  40.                 // ans is added to the variable ans
  41.                 ans += 2*min(nx,ny) * wt;
  42.             }
  43.         }
  44.  
  45.         // Just before leaving the node parent
  46.         return count[node];
  47.     }
  48.     int dfs()
  49.     {
  50.         /*
  51.         If you want to dynamically allocate an array of booleans, you need to do
  52.  
  53.             bool *arr = new bool[10];
  54.             You have to specify the array size.
  55.  
  56.  
  57.         The syntax for static allocation is
  58.  
  59.             bool arr[10];
  60.         */
  61.  
  62.         bool *visited = new bool[V+1];
  63.         int *count = new int[V+1];
  64.  
  65.         for(int i=1;i<V+1;i++)
  66.         {
  67.             visited[i] = false;
  68.             count[i] = 0;
  69.         }
  70.         int ans = 0;
  71.         dfsHelper(1,visited,count,ans);
  72.         return ans;
  73.     }
  74. };
  75.  
  76. int main()
  77. {
  78.     ios_base::sync_with_stdio(false);
  79.     cin.tie(0);
  80.     cout.tie(0);
  81.     int t;
  82.     cin >> t;
  83.     int i=1;
  84.     while (i<=t)
  85.     {
  86.         int n;
  87.         cin>>n;
  88.         Graph g(n);
  89.         for (int j=1;j<=n-1;j++)
  90.         {
  91.             int x,y,z;
  92.             cin>>x>>y>>z;
  93.             g.addEdge(x,y,z);
  94.         }
  95.         int req = g.dfs();
  96.         cout<<"Case #"<<i<<": "<< req<<endl;
  97.         i += 1;
  98.     }
  99. }
  100.  
Success #stdin #stdout 0s 4400KB
comments (?)
stdin
copy 
2
4
1 2 3
2 3 2
4 3 2
6
1 2 3
2 3 4
2 4 1
4 5 8
5 6 5
stdout
copy 
Case #1: 18
Case #2: 62
https://ideone.com/IXwJAx
problem HOLI, based on SPOJ submission 25989743 (CPP14), 2020-05-17 01:14:58
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!