fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Edge {
  8.     int s, e, cost;
  9.  
  10.     Edge(int s, int e, int cost) : s(s), e(e), cost(cost) { }
  11.  
  12.     bool operator < (const Edge &x) const {
  13.         return cost < x.cost;
  14.     }
  15. };
  16.  
  17. int N, M;
  18.  
  19. vector<Edge> edges;
  20.  
  21. int parent[50003];
  22.  
  23. int get_parent(int x) {
  24.     if (x == parent[x]) {
  25.         return x;
  26.     }
  27.     parent[x] = get_parent(parent[x]);
  28.     return parent[x];
  29. }
  30.  
  31. int process() {
  32.     sort(edges.begin(), edges.end());
  33.  
  34.     for (int i = 1; i <= N; i ++) {
  35.         parent[i] = i;
  36.     }
  37.  
  38.     int ret = 0;
  39.     for (int i = 0; i < M; i ++) {
  40.         int pa = get_parent(edges[i].s);
  41.         int pb = get_parent(edges[i].e);
  42.         if (pa == pb) {
  43.             continue;
  44.         }
  45.         ret += edges[i].cost;
  46.         parent[pa] = pb;
  47.     }
  48.  
  49.     return ret;
  50. }
  51.  
  52. int main() {
  53.     scanf("%d", &N);
  54.     scanf("%d", &M);
  55.  
  56.     for (int i = 0; i < M; i ++) {
  57.         int s, e, c;
  58.         scanf("%d %d %d", &s, &e, &c);
  59.         edges.push_back(Edge(s, e, c));
  60.     }
  61.  
  62.     printf("%d\n", process());
  63.  
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 3668KB
comments (?)
stdin
copy 
5
8
1 2 1
1 3 3
1 4 2
2 3 5
2 4 3
3 4 4
5 2 3
5 4 2
stdout
copy 
8
https://ideone.com/DxUbP6
language:
C++14 (gcc 8.3)
created:
7 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!