fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define in(t)  cin >> t
  3. #define in1(k, l) cin >> k >> l
  4. #define ll long long
  5. #define pb push_back
  6. #define mk make_pair
  7. #define pi pair<int, int>
  8. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  9. #define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
  10. #define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
  11. #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
  12. #define fi first
  13. #define se second
  14. using namespace std;
  15. const int N = 5e4 + 4;
  16. int w[N], deg[N];
  17. bool cmp(pair < int, pi > a, pair < int, pi> b) {
  18. 	if(a.fi != b.fi) return a.fi < b.fi;
  19. 	if(a.se.fi != b.se.fi) return a.se.fi > b.se.fi;
  20. 	if(a.se.se != b.se.se) return a.se.se > b.se.se;
  21. }
  22. int get(int cur) {
  23. 	if(cur == w[cur]) return cur;
  24. 	return w[cur] = get(w[cur]);
  25. }
  26. void merge(int a, int b) {
  27. 	if(rand() % 2) {
  28. 		swap(a, b);
  29. 	}
  30. 	a = get(a);
  31. 	b = get(b);
  32. 	w[a] = b;
  33. }
  34. int main() {
  35. 	int t;
  36. 	scanf("%d", &t);
  37. 	while(t--) {
  38. 		int n, m;
  39. 		scanf("%d%d", &n, &m);
  40. 		for(int i = 0; i <= n; i++) {
  41. 			w[i] = i;
  42. 			deg[i] = 0;
  43. 		}
  44. 		vector < pair < int, pi > > v, mst;
  45. 		for(int i = 0; i < m; i++) {
  46. 			int a, b, c;
  47. 			scanf("%d%d%d", &a, &b, &c);
  48. 			v.pb({c, {max(a, b), min(a, b)}});
  49. 		}
  50. 		sort(v.begin(), v.end(), cmp);
  51. 		ll ans = 0;
  52. 		for(int i = 0; i < m; i++) {
  53. 			int p1 = get(v[i].se.fi);
  54. 			int p2 = get(v[i].se.se);
  55. 			if(p1 == p2) continue;
  56. 			merge(v[i].se.fi, v[i].se.se);
  57. 			mst.pb(v[i]);
  58. 			ans += v[i].fi;
  59. 		}
  60. 		printf("%lld\n", ans);
  61. 		for(int i = 0; i < mst.size(); i++) {
  62. 			deg[mst[i].se.fi]++;
  63. 			deg[mst[i].se.se]++;
  64. 		}
  65. 		for(int i = 1; i <= n; i++) {
  66. 			printf("%d ", deg[i]);
  67. 		}
  68. 		cout << endl;
  69. 	}
  70. 	return 0;
  71. }
  72.  
  73.  
  74.  
Success #stdin #stdout 0s 3808KB
comments (?)
stdin
copy 
3
5 7
2 5 7
1 4 3
2 3 5
1 3 2
1 5 4
3 4 6
1 2 1
4 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 1 1000000000
1 1 1
2 3 1000000000
6 7
1 2 1
2 3 1
3 1 1
4 5 2
5 6 2
6 4 2
1 4 100000
stdout
copy 
10
4 1 1 1 1 
3000000000
1 1 2 2 
100006
2 1 2 2 1 2
https://ideone.com/5SQ7Lc
language:
C++14 (gcc 8.3)
created:
8 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!