fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 ( Độc cô cầu đặc )
  3.  *    created: 18.04.2026 03:56:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define ti tuple<int, int, int>
  16. #define fi first
  17. #define se second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define eb emplace_back
  21. #define pb push_back
  22. #define TASK " "
  23.  
  24. #define ms(a, x) memset(a, x, sizeof(a))
  25. #define all(a) a.begin(), a.end()
  26. #define All(a, n) a + 1, a + 1 + n
  27.  
  28. #define LOG 19
  29.  
  30. const int INF = 1e18;
  31. const int N = 2e4 + 5;
  32. const int maxn = 100 + 5;
  33. const int mod = 1e9 + 7;
  34.  
  35.  
  36. struct node{
  37. 	int kc, u;
  38. 	bool operator<(const node& other) const {
  39.         return kc > other.kc;
  40.     }
  41. };
  42. struct edge{
  43. 	int u, v, w, id;
  44. 	bool operator<(const edge& other) const {
  45.         return w > other.w;
  46.     }
  47. };
  48. edge edges[N];
  49. int n, m, k;
  50. int sz[N];
  51. int par[N];
  52. int p[N];
  53. void make_sets(int s){
  54.     sz[s] = 1;
  55.     par[s] = s;
  56. }
  57. int get(int a){
  58.     if(a == par[a]) return a;
  59.     return par[a] = get(par[a]);
  60. }
  61. bool union_sets(int a, int b){
  62.     a = get(a);
  63.     b = get(b);
  64.     if(a != b){
  65.         if(sz[a] < sz[b]){
  66.             // sz[a] > sz[b]
  67.             swap(a, b);
  68.         }
  69.         sz[a] += sz[b];
  70.         par[b] = a;
  71.         return 1;
  72.     }
  73.     return 0;
  74. }
  75. void nhap(){
  76. 	cin >> m >> n;
  77. 	for(int i = 0; i < m; i++){
  78.         int x, y, w;
  79.         cin >> x >> y >> w;
  80.         edges[i].u = x;
  81.         edges[i].v = y;
  82.         edges[i].w =  w;
  83.         edges[i].id = i + 1;
  84.     }
  85. 	sort(edges, edges + m);
  86. }
  87. void solve(){
  88. 	int ans =0;
  89. 	vector<int> res;
  90. 	for(int i = 1; i <= n; i++) make_sets(i);
  91. 	for(int i= 0; i < m; i++){
  92.         int u = edges[i].u;
  93.         int v = edges[i].v;
  94.         int w = edges[i].w;
  95.         int idx = edges[i].id;
  96.         if(union_sets(u, v)){
  97.             ans += w;
  98.             res.pb(idx);
  99.         }
  100.  
  101. 	}
  102. 	cout << ans << nn;
  103. 	for(int x : res){
  104.         cout << x << nn;
  105. 	}
  106. }
  107. signed main(){
  108. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109. 	nhap();
  110. 	solve();
  111. 	return 0;
  112. }
  113.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2
stdout
copy 
5
4
1
3
5
https://ideone.com/WO70gX
language:
C++14 (gcc 8.3)
created:
1 day 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!