fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<cmath>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<queue>
  7. #include<limits.h>
  8. using namespace std;
  9. class dsu
  10. {
  11. public:
  12. vector<int>parent;
  13. vector<pair<int,int>>rank;
  14. dsu(int y)
  15. {
  16. 	parent.assign(y+1,-1);
  17. 	rank.assign(y+1,{1,INT_MAX});
  18. }
  19. int find(int x)
  20. {
  21. if(parent[x]==-1) return x;
  22. return parent[x]=find(parent[x]);	
  23.  
  24. }	
  25. int unite(int i, int j,int w)
  26. {
  27. int s1=find(i);
  28. int s2=find(j);
  29. if(s1!=s2)
  30. {
  31. if(rank[s1].first>rank[s2].first) 
  32. {
  33. 	parent[s2]=s1;
  34. 	rank[s1].first+=rank[s2].first;
  35. 	rank[s1].second=min(rank[s1].second,w);
  36. }
  37. else {
  38. 	parent[s1]=s2;
  39. 	rank[s2].first+=rank[s1].first;
  40. 	rank[s2].second=min(rank[s2].second,w);
  41. }
  42. return 1;
  43. }
  44. return 0;
  45. }
  46.  
  47. };
  48. int main()
  49. {
  50. 	int t;
  51. 	cin>>t;
  52. 	while(t--)
  53. 	{
  54. 	int n;
  55. 	cin>>n;
  56. 	dsu Dsu(n);
  57. 	int m;
  58. 	cin>>m;
  59. 	priority_queue<vector<int>>edge;
  60. 	while(m--)
  61. 	{
  62. 	int x,y,z;
  63. 	cin>>x>>y>>z;	
  64.      edge.push({z,y,x});
  65. 	}
  66. 	int ans=0;
  67. 	while(!edge.empty())
  68. 	{
  69. 		auto edg=edge.top();
  70. 		int dist = edg[0];
  71. 		int v=edg[1];
  72. 		int u=edg[2];
  73. 		edge.pop();
  74. 		int s1=Dsu.find(u);
  75. 		int s2=Dsu.find(v);
  76. 		if(s1!=s2)
  77. 		{
  78. 		if(Dsu.rank[s1].second==dist)ans-=Dsu.rank[s1].first;
  79. 		if(Dsu.rank[s2].second==dist) ans-=Dsu.rank[s2].first;
  80. 		}
  81.  
  82. 			if(Dsu.unite(u,v,dist))
  83. 			{
  84. 			ans+=max(Dsu.rank[s1].first,Dsu.rank[s2].first);
  85. 	    	}
  86. 	    		for(auto it: Dsu.rank)
  87. 		cout<<it.first<<" "<<it.second<<endl;
  88. 		cout<<endl;
  89. 	}	
  90. cout<<ans<<endl;	
  91. }		
  92. 	/*
  93. 2
  94. 4 6
  95. 1 2 3
  96. 2 3 2
  97. 4 3 4
  98. 1 4 1
  99. 2 4 2
  100. 1 3 2
  101. 8 7
  102. 1 2 2
  103. 2 3 1
  104. 3 4 4
  105. 4 5 3
  106. 5 6 4
  107. 6 7 1
  108. 7 8 2
  109.  
  110. 	}*/
  111. }
Runtime error #stdin #stdout 3.63s 2084892KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EK63NM
language:
C++14 (gcc 8.3)
created:
1 year 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!