fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class UF {
  6.   int *id, cnt, *sz;
  7.   public:
  8. 	// Create an empty union find data structure with N isolated sets.
  9. 	UF(int N) {
  10. 	    cnt = N; id = new int[N]; sz = new int[N];
  11. 	    for (int i = 0; i<N; i++)  id[i] = i, sz[i] = 1; }
  12. 	// ~UF() { delete[] id; delete[] sz; }
  13.  
  14. 	// Return the id of component corresponding to object p.
  15. 	int find(int p) {
  16. 	    int root = p;
  17. 	    while (root != id[root])    root = id[root];
  18. 	    while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
  19. 	    return root;
  20. 	}
  21. 	// Replace sets containing x and y with their union.
  22. 	void merge(int x, int y) {
  23. 	    int i = find(x); int j = find(y); if (i == j) return;
  24. 	    // make smaller root point to larger one
  25. 	    if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
  26. 	    else { id[j] = i, sz[i] += sz[j]; }
  27. 	    cnt--;
  28. 	}
  29. 	// Are objects x and y in the same set?
  30. 	bool connected(int x, int y) { return find(x) == find(y); }
  31. 	// Return the number of disjoint sets.
  32. 	int count() { return cnt; }
  33. };
  34. // https://stackoverflow.com/a/33594182
  35.  
  36.  
  37. int main()
  38. {
  39. 	int t;
  40. 	cin>>t;
  41. 	while(t--) {
  42. 		int n,r,cshop,croad;
  43. 		cin>>n>>r>>cshop>>croad;
  44. 		if(cshop<=croad) {
  45. 			cout<<(n*(long long)cshop)<<'\n';
  46. 			int u,v;
  47. 			while(r--) {
  48. 				cin>>u>>v;
  49. 			}
  50. 		}
  51. 		else {
  52. 			UF dis(n);
  53. 			int u,v;
  54. 			while(r--) {
  55. 				cin>>u>>v;
  56. 				dis.merge(u,v);
  57. 			}
  58. 			int count=dis.count();
  59. 			cout<<(croad*(long long)(n-count)+(long long)cshop*count)<<'\n';
  60. 		}
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
2
3 3 2 1
1 2
3 1
2 3
6 6 2 5
1 3
3 4
2 4
1 2
2 3
5 6
stdout
copy 
4
12
https://ideone.com/mLEhd7
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!