fork download
copy 
  1. //Krushkal Algorithm
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. vector<int>v;
  6. class Edge {
  7. 	public:
  8. 	int src;
  9. 	int dest;
  10. 	int wt;
  11. };
  12.  
  13. bool cmp(Edge e1, Edge e2) {
  14. 	return e1.wt > e2.wt;
  15. }
  16.  
  17. int findParent(int ch, int *parent) {
  18. 	if(parent[ch] == ch) {
  19. 		return ch;
  20. 	} else {
  21. 		return findParent(parent[ch],parent);
  22. 	}
  23. }
  24.  
  25. void krushkal(Edge *input, int n, int m) {
  26. 	sort(input+1,input+m+1, cmp);
  27. 	int parent[n+1];
  28. 	int count = 1;
  29. 	for(int i=1;i<=n;i++) parent[i] = i;
  30. 	Edge *output = new Edge[n+1];
  31. 	int i = 1;
  32. 	while(count != n) {
  33. 		Edge currEdge = input[i++];
  34. 		int srcParent = findParent(currEdge.src, parent);
  35. 		int destParent = findParent(currEdge.dest, parent);
  36. 		if(srcParent != destParent) {
  37. 			output[count++] = currEdge;
  38. 			parent[srcParent] = destParent;
  39. 		} else {
  40. 			v.push_back(currEdge.wt);
  41. 		}
  42. 	}
  43. }
  44.  
  45. int main() {
  46. 	int n,m,s;
  47. 	cin>>n>>m>>s;
  48. 	Edge *input = new Edge[m+1];
  49. 	for(int i=1;i<=m;i++) {
  50. 		cin >> input[i].src >> input[i].dest >> input[i].wt;
  51. 	}
  52. 	krushkal(input,n,m);
  53. 	sort(v.begin(),v.end());
  54. 	int ans = 0, i = 0;
  55. 	for(i=0;i<v.size();i++) {
  56. 		if(ans+v[i]<=s) {
  57. 			ans+=v[i];
  58. 		} else {
  59. 			break;
  60. 		}
  61. 	}
  62. 	cout<<i<<" "<<ans;
  63. 	return 0;
  64. }
Success #stdin #stdout 0s 4276KB
comments (?)
stdin
copy 
6 7 10
1 2 3
1 3 3
2 3 3
3 4 1
4 5 5
5 6 4
4 6 5
stdout
copy 
2 7
https://ideone.com/NxrMrt
language:
C++14 (gcc 8.3)
created:
5 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!