fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int >ii;
  4. typedef long long ll;
  5. vector<pair<int,ii> >g;
  6. vector<int>parent;
  7. vector<int>rnk;
  8. vector<ii>mst;
  9. ll tot_wt;
  10. int find_(int u){
  11.     if(u!=parent[u])
  12.         parent[u]=find_(parent[u]);
  13.     return parent[u];
  14. }
  15.  
  16. void _union(int x,int y){
  17.     int xset=find_(x);
  18.     int yset=find_(y);
  19.  
  20.     if(rnk[xset]>rnk[yset])
  21.         parent[yset]=xset;
  22.     if(rnk[yset]>rnk[xset])
  23.         parent[xset]=yset;
  24.     else{
  25.         parent[yset]=xset;
  26.         rnk[xset]++;
  27.     }
  28.  
  29. }
  30.  
  31. ll kruskal(ii k){
  32.     tot_wt=0;
  33.     for(int i=0;i<g.size();i++){
  34.  
  35.         int u=g[i].second.first,v=g[i].second.second;
  36.         if((u==k.first)&& (v==k.second)){
  37.             //cout<<u<<" "<<v<<"\n";
  38.             continue;
  39.             }
  40.         int uset=find_(u),vset=find_(v);
  41.  
  42.         if(uset!=vset){
  43.             tot_wt+=g[i].first;
  44.             _union(uset,vset);
  45.             //cout<<u<<" "<<v<<"\n";
  46.             if(k.first==-1&&k.second==-1)
  47.                 mst.push_back({u,v});
  48.         }
  49.     }
  50.  
  51. return tot_wt;
  52. }
  53.  
  54. int main(){
  55.     int t;cin>>t;
  56.     while(t--){
  57.     int n,m;cin>>n>>m;
  58.     g.assign(m,pair<int,ii>());
  59.     parent.assign(n+1,0);
  60.     rnk.assign(n+1,0);
  61.     for(int i=0;i<m;i++){
  62.         int a,b,w;cin>>a>>b>>w;
  63.         g[i]={w,{a,b}};
  64.     }
  65.     sort(g.begin(),g.end());
  66.     for(int i=1;i<=n;i++)
  67.         parent[i]=i;
  68.     cout<<kruskal({-1,-1})<<" ";
  69.  
  70.  
  71.  
  72.     ll swt=INT_MAX;
  73.     for(int i=0;i<mst.size();i++){
  74.         //cout<<mst[i].first<<" "<<mst[i].second<<"\n";
  75.         for(int i=0;i<=n;i++)
  76.         parent[i]=i;
  77.     for(int i=0;i<=n;i++)
  78.         rnk[i]=0;
  79.         swt=min(swt,kruskal(mst[i]));
  80.  
  81.     }
  82.     cout<<swt<<"\n";}
  83.  
  84. }
  85.  
Time limit exceeded #stdin #stdout 5s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0n3rQJ
language:
C++14 (gcc 8.3)
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!