fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int cost[100005] , parent[100005];
  4. int find1( int a )
  5. {
  6. 	//a and parent of a are not equal that means that a's is not root and we
  7. 	//need to find the root parent of a and assign a to it's root parent inorder
  8. 	//decrease the height of the tree.
  9. 	if( a!=parent[a])
  10. 	{
  11. 		//we will find the root parent and assign it the parent of a
  12. 		parent[a]=find1(parent[a]);
  13. 	}
  14. 	return parent[a];
  15. }
  16.  
  17. void union1( int a , int b , int rank[])
  18. {
  19. 	int pa , pb;
  20. 	pa=find1(a); //getting root parent of a 
  21. 	pb=find1(b); //getting root parent of b
  22. 	if( pa==pb )
  23. 	{
  24. 		//if both the element are in the same tree/ set.
  25. 		return;
  26. 	}
  27. 	if( rank[pa] > rank[pb] )
  28. 	{
  29. 		//if rank of one tree is more than the rank of other we attach the smaller
  30. 		//tree to the bigger tree and there is no change in the rank because there
  31. 		//is no increase in the height of the tree.
  32. 		parent[pb]=pa;
  33.  
  34. 	}
  35. 	else 
  36. 	{
  37.  
  38. 		parent[pa]=pb;
  39. 		if( rank[pa]==rank[pb] )
  40. 		{
  41. 			// if rank of both the trees are equal there is change in height of the 
  42. 			//tree so we increase the rank by 1.
  43. 			rank[pb]++;
  44. 		}
  45. 	}
  46.  
  47. }
  48.  
  49. void find2( int x )
  50. {
  51.  
  52. 	int root_parent;
  53. 	//finding the root parent of x and also making ever other element in the way 
  54. 	// to point to root parent
  55. 	root_parent=find1(x);
  56. 	// value of root parent is more than an element we interchange the value only
  57. 	//if the value of element is >=0 OR if the value of root parent is <0 and 
  58. 	//value of an element is >=0  then we interchange the value 
  59.    if( (cost[x]<cost[root_parent] && cost[x]>=0) || (cost[root_parent]<0 && cost[x]>=0))
  60.    {
  61.    	cost[root_parent]=cost[x];
  62.    }
  63. }
  64.  
  65. int main() {
  66. 	// your code goes here
  67. 	std::ios_base::sync_with_stdio(false);
  68. 	int n , m , a , b, min=100005 , sum=0 , count=0 , j=1;
  69. 	cin>>n>>m; //taking n and m as input
  70. 	int rank[100005];
  71. 	bool vis[n+1];
  72. 	for( int i=1 ; i<=n ; i++)
  73. 	{
  74. 		//assigning initial value to rank , parent and visited array
  75. 		rank[i]=0;   
  76. 		parent[i]=i;
  77. 		vis[i]=false;
  78. 	}
  79. 	for( int i=1 ; i<=m ; i++)
  80. 	{
  81. 		cin>>a>>b;
  82. 		//making a and b in the same set / tree.
  83. 		union1(a,b,rank);
  84. 	}
  85. 	for( int i=1 ; i<=n ; i++)
  86. 	{
  87. 		//taking cost of each portal
  88. 		cin>>cost[i];
  89. 	}
  90. 	for( int i=1 ; i<=n ; i++)
  91. 	{
  92. 		//making the each element to point to it's root parent and no other element
  93. 		//so that we can have a uniform parent array pointing only to it's root
  94. 		//parent(reason is ahead)
  95. 		find2(i);
  96. 	}
  97.  
  98. 	for( int i=1 ; i<=n ; i++)
  99. 	{
  100. 		//i m visiting root parent of n different disjoint sets once and 
  101. 		//checking the minimum value of the root parent if any of the root 
  102. 		//value is <0 and more than 1 disjoint set is formed then the output
  103. 		//will be -1 otherwise the output can 0 or sum+(count-2)*min .
  104. 		if(vis[parent[i]] == false)
  105. 		{
  106. 			//cout<<1;
  107. 			if( cost[parent[i]]<0 )
  108. 			{
  109. 				j=0;
  110. 			}
  111. 		   sum+=cost[parent[i]];
  112. 		   vis[parent[i]]=true;
  113. 		   if(cost[parent[i]]<min )
  114. 		   {
  115. 		   	min=cost[parent[i]];
  116. 		   }
  117. 		   count++;
  118. 		}
  119. 	}
  120. 	//cout<<count<<" ";
  121. 	if(count!=1)
  122. 	{
  123. 		if(j==0)
  124. 		{
  125. 			cout<<"-1\n";
  126. 		}
  127. 		else
  128. 		{
  129. 			count=(count-2)*min;
  130. 		   cout<<sum+count<<"\n";
  131. 		}
  132. 	}
  133. 	else
  134. 	{
  135. 		cout<<"0\n";
  136. 	}
  137.  
  138. 	return 0;
  139. }
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
6 1
2 3
1
-11
1
1
1
1
stdout
copy 
8
https://ideone.com/OUBDtL
language:
C++14 (gcc 8.3)
created:
6 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!