fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define PI acos(-1)
  3. using namespace std;
  4. #define MX 10001
  5. int parent[MX];
  6. struct edge
  7. {
  8.     int u;
  9.     int v;
  10.     int w;
  11. };
  12. vector < edge > v;
  13. vector<int>edges;
  14. int secondmst[202],xx=0;
  15. bool flag1,flag2;
  16. bool comp(edge x,edge y)
  17. {
  18.     if(x.w<y.w)return true;
  19.     else
  20.         return false;
  21. }
  22. int Find(int x)
  23. {
  24.     if(parent[x]==x)return x;
  25.     parent[x]=Find(parent[x]);
  26.     return parent[x];
  27. }
  28. int mst(int n)
  29. {
  30.     sort(v.begin(),v.end(),comp);
  31.     for(int i=1; i<=n; i++)parent[i]=i;
  32.     int c=0,ans=0,l=v.size();
  33.     if(l==0)flag1=true;
  34.     for(int i=0; i<l; i++)
  35.     {
  36.  
  37.         int p=Find(v[i].u);
  38.         int q=Find(v[i].v);
  39.  
  40.         if(p!=q)
  41.         {
  42.  
  43.  
  44.             edges.push_back(i);
  45.  
  46.  
  47.             parent[p]=q;
  48.  
  49.             ++c;
  50.             ans += v[i].w;
  51.  
  52.             if(c==n-1)
  53.             {
  54.                 flag1=true;
  55.                 break;
  56.  
  57.             }
  58.         }
  59.     }
  60.  
  61.     return ans;
  62. }
  63. int secondBestMst(int n)
  64. {
  65.     int best2=INT_MAX,c=0;
  66.     int len=edges.size();
  67.     for(int k=0; k<len; k++)
  68.     {
  69.         for(int i=1; i<=n; i++)
  70.         {
  71.             parent[i]=i;
  72.         }
  73.         int s=0;
  74.         c=0;
  75.         for(int i=0; i<v.size(); i++)
  76.         {
  77.             if(edges[k]==i)continue;
  78.             int p=Find(v[i].u);
  79.             int q=Find(v[i].v);
  80.             if(p!=q)
  81.             {
  82.  
  83.                 parent[p]=q;
  84.                 c++;
  85.                 s += v[i].w;
  86.                 if(c==n-1)
  87.                 {
  88.                     if(best2>s)
  89.                     {
  90.                         best2=s;
  91.                         secondmst[xx++]=best2;
  92.                     }
  93.                     flag2=true;
  94.                     break;
  95.  
  96.                 }
  97.  
  98.  
  99.  
  100.             }
  101.  
  102.         }
  103.  
  104.     }
  105.  
  106.     return best2;
  107. }
  108. int main()
  109. {
  110.  
  111.     // freopen("input.txt","r",stdin);
  112.     // freopen("output.txt","w",stdout);
  113.     int t,n,m,x,y,z,k=0;
  114.     scanf("%d",&t);
  115.  
  116.     while(t--)
  117.     {
  118.         scanf("%d%d",&n,&m);
  119.         for(int i=1; i<=m; i++)
  120.         {
  121.             scanf("%d%d%d",&x,&y,&z);
  122.             if(x>y)swap(x,y);
  123.             edge get;
  124.             get.u=x;
  125.             get.v=y;
  126.             get.w=z;
  127.             v.push_back(get);
  128.  
  129.         }
  130.  
  131.  
  132.  
  133.  
  134.  
  135.         int ans=mst(n);
  136.         int ans2=secondBestMst(n);
  137.  
  138.         if(n==1)flag1=true;
  139.         // cout<<ans<<"   "<<ans2<<endl;
  140.         if(flag1&&!flag2)
  141.             printf("Case #%d : No second way\n",++k);
  142.         else if(!flag1)
  143.             printf("Case #%d : No way\n",++k);
  144.         else
  145.         {
  146.             sort(secondmst,secondmst+xx);
  147.             printf("Case #%d : %d\n",++k,secondmst[0]);
  148.  
  149.  
  150.         }
  151.  
  152.         flag1=false,flag2=false;
  153.         memset(secondmst,0,sizeof(secondmst));
  154.         xx=0;
  155.         v.clear();
  156.         edges.clear();
  157.  
  158.  
  159.  
  160.     }
  161.  
  162.  
  163.  
  164.     return 0;
  165. }
  166.  
Success #stdin #stdout 0s 3520KB
comments (?)
stdin
copy 
1
4 7
3 4 486
2 4 851
4 1 705
3 2 8
2 1 59
4 1 73
2 1 114
stdout
copy 
Case #1 : 195
https://ideone.com/m5lFmo
language:
C++ (gcc 8.3)
created:
7 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!