fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int sz[200000], par[200000];
  4. vector<pair<int, pair<int,int>>> mp;
  5.  
  6. int fs(int a){
  7.     return par[a] == a ? a : (par[a] = fs(par[a]));
  8. }
  9.  
  10. int us(int a, int b){
  11.     a = fs(a);
  12.     b = fs(b);
  13.     if(a != b){
  14.         par[b] = a;
  15.         sz[a] += sz[b];
  16.         return 1;
  17.     }
  18.     return 0;
  19. }
  20.  
  21. int main() {
  22.     int m, n, w, x, y; 
  23.     long long s, tol = 0; cin >> n >> m >> s;
  24.     for(int i = 0; i < m; i++){
  25.         cin >> x >> y >> w;
  26.         mp.push_back({w, {x, y}});
  27.         tol += w;
  28.     }
  29.     sort(mp.begin(), mp.end(), greater<vector<pair<int, pair<int,int>>>>());
  30.     for(int i = 1; i <= n; i++){
  31.         par[i] = i;
  32.         sz[i] = 1;
  33.     }
  34.     bool 
  35.     long long cnt = 0, tmp = 0;
  36.     for(auto i: mp){
  37.         if(cnt == n - 1 s + tmp >= tol) break;
  38.         if(us(i.second.first, i.second.second)){
  39.             cnt++;
  40.             tmp += i.first;
  41.  
  42.         }
  43.     }
  44.     cout << s;
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3 3
1 2 5
1 3 10
2 3 5
stdout
copy 
5
https://ideone.com/N9gb1y
language:
C++14 (clang 8.0)
created:
2 days 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!