fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. struct edge
  7. {
  8.     int src;
  9.     int dest;
  10.     int wt;
  11.     edge(int a,int b,int c)
  12.     {
  13.         src = a;dest = b; wt = c;
  14.     }
  15. };
  16. bool compare(edge *a,edge *b)
  17. {
  18.     if(a->wt <= b->wt)
  19.         return true;
  20.     return false;
  21. }
  22. int find(vector<int> &parent,int a)
  23. {
  24.     if(parent[a]==-1)
  25.         return a;
  26.     return find(parent,parent[a]);
  27. }
  28. void Union(vector<int> &parent,int a,int b)
  29. {
  30.     int as = find(parent,a);
  31.     int bs = find(parent,b);
  32.     parent[as]=bs;
  33. }
  34. bool iscycle(edge *a,vector<int> &parent)
  35. {
  36.     int ax = find(parent,a->src);
  37.     int bx = find(parent,a->dest);
  38.     if(ax==bx)
  39.         return true;
  40.     else
  41.     {
  42.         Union(parent,ax,bx);
  43.         return false;
  44.     }
  45. }
  46. int solve(int A, vector<vector<int> > &B) {
  47.     edge **arr = new edge*[B.size()];
  48.     for(int i=0;i<B.size();i++)
  49.     {
  50.         arr[i] = new edge(B[i][0],B[i][1],B[i][2]);
  51.     }
  52.  
  53.     sort(arr,arr+B.size(),compare);
  54.     /*for(int i=0;i<B.size();i++)
  55.     	cout<<arr[i]->src<<" "<<arr[i]->dest<<" "<<arr[i]->wt<<endl;*/
  56.     int ed = 0;
  57.     int ans = 0;
  58.     vector<int> parent;
  59.     parent.resize(A,-1);
  60.     /*for(int i=0;i<A;i++)
  61.     	cout<<parent[i]<<" ";
  62.     cout<<endl;*/
  63.     for(int i=0;i<B.size();i++)
  64.     {
  65.         if(iscycle(arr[i],parent)==false)
  66.         {
  67.             ans += arr[i]->wt;
  68.             ed++;
  69.         }
  70.         if(ed==A-1)
  71.             return ans;
  72.     }
  73. }
  74. int main()
  75. {
  76. 	int v,e;
  77. 	cin>>v>>e;
  78. 	vector<vector<int> > B;
  79. 	B.resize(e);
  80. 	for(int i=0;i<e;i++)
  81. 		B[i].resize(3);
  82. 	for(int i=0;i<e;i++)
  83. 	{
  84. 		int a,b,wt;
  85. 		cin>>a>>b>>wt;
  86. 		B[i][0]=a;
  87. 		B[i][1]=b;
  88. 		B[i][2]=wt;
  89. 	}
  90. 	/*for(int i=0;i<e;i++)
  91. 	{
  92. 		//int a,b,wt;
  93. 		//cin>>a>>b>>wt;
  94. 		cout<<B[i][0]<<" "<<B[i][1]<<" "<<B[i][2]<<endl;
  95. 	}*/
  96. 	cout<<solve(v,B)<<endl;
  97. }
  98.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
4 5
1 2 1 
2 3 4
1 4 3
4 3 2
1 3 10
stdout
copy 
6
https://ideone.com/xYcQBb
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!