fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int par[105];
  4. int ran[105];
  5. struct edge
  6. {
  7.     int from;
  8.     int to;
  9.     int cost;
  10.     int ind;
  11. };
  12. bool cmp(edge a, edge b)
  13. {
  14.     return a.cost<b.cost;
  15. }
  16. void ini(int n)
  17. {
  18.     for (int i = 0; i<n; ++i)
  19.     {
  20.         par[i] = i;
  21.         ran[i] =0;
  22.     }
  23. }
  24. int find_set(int i)
  25. {
  26.     if (i==par[i])return i;
  27.     return par[i] = find_set(par[i]);
  28. }
  29. int join(int i, int j)
  30. {
  31.     i = find_set(i);
  32.     j = find_set(j);
  33.     if (i!=j)
  34.     {
  35.         if (ran[i]>ran[j])
  36.         {
  37.             ran[i]+=ran[j];
  38.             par[j] = i;
  39.         }
  40.         else
  41.         {
  42.             ran[j]+=ran[i];
  43.             par[i] = j;
  44.         }
  45.         return 1;
  46.     }
  47.     return 0;
  48. }
  49. int main()
  50. {
  51.     int t;
  52.     cin>>t;
  53.     while (t--)
  54.     {
  55.         int n,m;
  56.         cin>>n>>m;
  57.         ini(n);
  58.         vector<edge> v;
  59.         for (int i = 0; i<m; ++i)
  60.         {
  61.             int a,b,c;
  62.             a--;
  63.             b--;
  64.             cin>>a>>b>>c;
  65.             v.push_back({a,b,c,i});
  66.         }
  67.         sort(v.begin(),v.end(),cmp);
  68.         vector<int> ans;
  69.         int cnt = 0;
  70.         int k = 0;
  71.         int c = 0;
  72.         vector<edge> touse;
  73.         int fmin = INT_MAX;
  74.         for (int i = 0; i<v.size(); ++i)
  75.         {
  76.             if (join(v[i].from,v[i].to))
  77.             {
  78.                 touse.push_back(v[i]);
  79.                 cnt+=v[i].cost;
  80.                 c++;
  81.             }
  82.         }
  83.         if (c==n-1)fmin=cnt;
  84.         ini(n);
  85.         cnt= 0;
  86.         c = 0;
  87.         int smin = INT_MAX;
  88.         for (int i = 0; i<touse.size(); ++i)
  89.         {
  90.             k = touse[i].ind;
  91.             for (int j = 0; j<v.size(); ++j)
  92.             {
  93.                 if (v[j].ind==k)continue;
  94.                 if (join(v[j].from,v[j].to))
  95.                 {
  96.                     cnt+=v[j].cost;
  97.                     c++;
  98.                 }
  99.             }
  100.             if (c!=n-1)cnt = INT_MAX;
  101.             if (cnt<smin)
  102.             {
  103.                 smin = cnt;
  104.             }
  105.             ini(n);
  106.             cnt= 0;
  107.             c = 0;
  108.         }
  109.         cout<<fmin<<" "<<smin<<endl;
  110.         cout<<endl;
  111.     }
  112. }
  113.  
Runtime error #stdin #stdout 0.01s 5548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/spXa9w
language:
C++14 (gcc 8.3)
created:
1 year 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!