fork download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<cassert>
  5. #include<string>
  6. #include<algorithm>
  7. #include<vector>
  8. #include<map>
  9. #include<set>
  10. #include<numeric>
  11. #include<cmath>
  12. #include<iterator>
  13. #include<list>
  14. #include<limits.h>
  15.  
  16. #define ll long long
  17.  
  18. using namespace std;
  19.  
  20. /*
  21. #define getcx getchar_unlocked
  22. inline void inp( int &n )//fast input function
  23. {
  24.    n=0;
  25.    int ch=getcx();int sign=1;
  26.    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
  27.  
  28.    while(  ch >= '0' && ch <= '9' )
  29.            n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
  30.    n=n*sign;
  31. }
  32. */
  33.  
  34.  
  35. ll id[100005];
  36. ll size[100005];
  37. ll cost[100005];
  38. ll pairs[1000005][2];
  39.  
  40. int find_parent(ll id[],int i) //with path compression
  41. {
  42.  
  43. 	while(i!=id[i])
  44. 	{
  45. 		id[i]=id[id[i]];
  46. 		i=id[i];
  47. 	}
  48. 	 return i;	
  49. }
  50.  
  51.  
  52. void quick_union(ll id[],ll cost[],ll size[],int p,int q,int n )
  53. {
  54. 	p=find_parent(id,p);
  55. 	q=find_parent(id,q);
  56.  
  57.  
  58. 	if(p==q) return;
  59.  
  60. 	if(size[p]>size[q])
  61. 	{
  62. 		id[q]=p;
  63. 		size[p]+=size[q];
  64.  
  65. 		if(cost[p]>cost[q])
  66. 		cost[p]=cost[q];
  67. 	}
  68.  
  69. 	else
  70. 	{
  71. 		id[p]=q;
  72. 		size[q]+=size[p];
  73.  
  74. 		if(cost[q]>cost[p])
  75. 		cost[q]=cost[p];
  76.  
  77. 	}
  78.  
  79. }
  80.  
  81.  
  82. void print_all(ll id[], ll cost[], ll size[],int n)
  83. {	
  84. 	int i;
  85. 	for(i=1;i<=n;i++)
  86. 	{
  87. 		cout<<id[i]<<" ";
  88. 	}
  89.  
  90. 	cout<<endl;
  91.  
  92. 	for(i=1;i<=n;i++)
  93. 	{
  94. 		cout<<size[i]<<" ";
  95. 	}
  96.  
  97. 	cout<<endl;
  98.  
  99. 	for(i=1;i<=n;i++)
  100. 	{
  101. 		cout<<cost[i]<<" ";
  102. 	}
  103. }
  104.  
  105. int main()
  106. {
  107.  
  108.  
  109. 	ll i, n, m, min_cost=INT_MAX, a, b,amt=0,count=0;
  110.  
  111. 	cin>>n>>m;
  112.  
  113.  
  114.  
  115. 	for(i=1;i<=n;i++)
  116. 	{
  117. 		id[i]=i;
  118. 		size[i]=1;
  119. 		cost[i]=INT_MAX;
  120. 	}
  121.  
  122. 	for(i=0;i<m;i++)
  123. 	{
  124. 		cin>>pairs[i][0]>>pairs[i][1];
  125. 	}
  126.  
  127. 	for(i=1;i<=n;i++)
  128. 	{
  129. 		int c;
  130. 		cin>>c;
  131. 		if(c>=0)
  132. 			cost[i]=c;
  133. 	}
  134.  
  135. 	for(i=0;i<m;i++)
  136. 	{
  137. 		a=pairs[i][0];
  138. 		b=pairs[i][1];
  139.  
  140. 		quick_union(id,cost,size,a,b,n);
  141. 	} 
  142.  
  143. 	for(i=1;i<=n;i++)
  144. 	{
  145. 		a=i;	
  146. 		while(id[a]!=a) a=id[a];	
  147. 		id[i]=a;
  148. 	}
  149.  
  150. 	//print_all(id,cost,size,n);
  151.  
  152.  
  153. 	for(i=1;i<=n;i++)
  154. 	{
  155. 		if(i==id[i])
  156. 		{
  157.  
  158. 			if(cost[i]==INT_MAX)
  159. 			{
  160. 				cout<<"-1"<<endl;
  161. 				return 0;
  162. 			}
  163.  
  164. 			count++;
  165.  
  166. 			if(min_cost>cost[i])
  167. 				min_cost=cost[i];
  168. 			amt+=cost[i];
  169.  
  170. 		}
  171. 	}
  172.  
  173. 	if(count==1)
  174. 	{
  175. 		cout<<"0"<<endl;
  176. 		return 0;
  177. 	}
  178.  
  179. 	amt+=(count-2)*min_cost;
  180.  
  181. 	cout<<amt<<endl;
  182.  
  183. return 0;
  184.  
  185. }
Success #stdin #stdout 0s 21320KB
comments (?)
stdin
copy 
7 4 
1 2 
2 3 
1 3 
5 6 
3 -1 -1 2 6 8 4
stdout
copy 
19
https://ideone.com/sijEZH
language:
C++ (gcc 8.3)
created:
9 years 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!