fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3.  
  4. #define gc getchar
  5. #define pc putchar
  6.  
  7. using namespace std;
  8.  
  9. /*#include <ext/pb_ds/tree_policy.hpp>
  10. #include <ext/pb_ds/detail/standard_policies.hpp>
  11. #include <ext/pb_ds/assoc_container.hpp>
  12.  
  13. using namespace __gnu_pbds;
  14. */
  15.  
  16. /*
  17.         two functions for policy based data structure. it is
  18.  
  19.                 find_by_order() and order_of_key().
  20.  
  21.         The first returns an iterator to the k-th largest element (counting from zero),
  22.         the second returns the number of items in a set that are strictly smaller than our item
  23.  
  24. */
  25.  
  26. #define vi vector<int>
  27. #define si set<int>
  28. #define vs vector<string>
  29. #define pii pair<int,int>
  30. #define vpi vector<pii>
  31. #define pri priority_queue<int>
  32. #define rev_pri priority_queue<int,vector<int>,greater<int> >
  33. #define mpi map<int,int>
  34. #define i64 long long int
  35. #define endl '\n'
  36. #define pi acos(-1)
  37. #define all(v) v.begin(),v.end()
  38. #define pb push_back
  39. #define mp make_pair
  40. #define mod 1000000007
  41. #define For(i,n) for(int i=0;i<n;i++)
  42. #define Rep(i,x,y) for(int i=x;i<=y;i++)
  43. #define eps 1e-8
  44. #define ff first
  45. #define ss second
  46. #define mem(a,b) memset(a,b,sizeof(a))
  47. #define min3(a,b,c) min(a,min(b,c))
  48. #define max3(a,b,c) max(a,max(b,c))
  49. #define READ freopen("input.txt", "r", stdin)
  50. #define sz size()
  51. #define dbg(x) printf("yo is %d!\n",x)
  52. #define dbg2(x,y) printf("yo is %d! and %d!\n",x,y)
  53. #define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
  54. #define sqr(a) (a) * (a)
  55. #define clr clear()
  56. #define CASE(a) printf("Case %d:\n",a)
  57. #define sf(n) scanf("%d", &n)
  58. #define sff(a,b) scanf("%d %d", &a, &b)
  59. #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
  60.  
  61. //int dx[] = {0,1,0,-1};
  62. //int dy[] = {1,0,-1,0};
  63. //int dx[] = { -1, -1,  0, 1, 1, 1,  0, -1 };
  64. //int dy[] = {  0, -1, -1, -1,  0, 1, 1, 1 };
  65. //int dxK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
  66. //int dyK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
  67.  
  68. //functions
  69.  
  70. //i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}
  71.  
  72. //inline void fastRead(i64 *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}
  73.  
  74. //inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}
  75.  
  76. //i64 bigmod(i64 num,i64 n){if(!n)return 1;i64 x=(bigmod(num,n/2)*bigmod(num,n/2))%mod;if(n%2)x=(x*num)%mod;return x;}
  77.  
  78. //i64 modinverse(i64 num){return bigmod(num,mod-2);}
  79.  
  80. //void combination(int pos,int last){if(pos==k+1){for(int i=1;i<=k;i++)cout << tem[i];cout << endl;return;}
  81. //for(int i=last+1;i<=n-k+pos;i++){tem[pos] = num[i-1];combination(pos+1,i);}}
  82. //i64 power(i64 value, i64 base){i64 result = 1;For(i,base)result *= value;return result;}
  83. //int Set(int N,int pos){return N = (1<<pos);}
  84. //int reset(int N,int pos){return N &= (~(1<<pos));}
  85. //bool check(int N,int pos){return (bool)(N & (1<<pos));}
  86.  
  87. //typedef tree< int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > Set;
  88.  
  89. int vis[205];
  90. vpi adj[205], tree[205];
  91.  
  92. int prim(int k)
  93. {
  94.     mem(vis,0);
  95.  
  96.     priority_queue<pair<int,pii>, vector<pair<int,pii> >, greater<pair<int,pii> > > pq;
  97.  
  98.     pq.push(mp(0,mp(k,-1)));
  99.  
  100.     int ret = 0;
  101.  
  102.     while(!pq.empty())
  103.     {
  104.         pair<int,pii> p = pq.top();
  105.         pq.pop();
  106.  
  107.         int u = p.ss.ff;
  108.         int pr = p.ss.ss;
  109.  
  110.         if(vis[u])
  111.             continue;
  112.  
  113.         ret += p.ff;
  114.         vis[u] = 1;
  115.         if(pr!=-1)
  116.         {
  117.             tree[u].pb(mp(pr,p.ff));
  118.             tree[pr].pb(mp(u,p.ff));
  119.         }
  120.  
  121.         For(i,adj[u].sz)
  122.         {
  123.             int v = adj[u][i].ff;
  124.             if(!vis[v])
  125.                 pq.push(mp(adj[u][i].ss,mp(v,u)));
  126.         }
  127.     }
  128.     return ret;
  129. }
  130.  
  131. int main()
  132. {
  133.     int t;
  134.     sf(t);
  135.     Rep(tc,1,t)
  136.     {
  137.         int n,w;
  138.         sff(n,w);
  139.         mem(adj,NULL);
  140.         CASE(tc);
  141.         while(w--)
  142.         {
  143.             int a,b,c;
  144.             sfff(a,b,c);
  145.             adj[a].pb(mp(b,c));
  146.             adj[b].pb(mp(a,c));
  147.  
  148.             int flag = 1;
  149.             int ans = prim(a);
  150.  
  151.             Rep(i,1,n)
  152.             {
  153.                 if(!vis[i])
  154.                     flag = 0;
  155.                 else
  156.                     adj[i] = tree[i];
  157.             }
  158.  
  159.  
  160.             if(flag)
  161.                 printf("%d\n",ans);
  162.             else
  163.                 printf("-1\n");
  164.             //Rep(i,1,n)
  165.                 //dbg(adj[i].sz);
  166.             mem(tree,NULL);
  167.         }
  168.     }
  169.  
  170.     return 0;
  171. }
  172.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
2
4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2
4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2
stdout
copy 
Case 1:
-1
-1
-1
14
12
8
Case 2:
-1
-1
-1
14
12
8
https://ideone.com/66n6Zl
language:
C++14 (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!