Advertisement
Guest User

B

a guest
Dec 17th, 2017
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. struct edge {
  7.     int u, v, pos;
  8.     ll w;
  9.  
  10.     edge() = default;
  11.  
  12.     edge(int _u, int _v, ll _w, int _pos) {
  13.         u = _u, v = _v, w = _w, pos = _pos;
  14.     }
  15.  
  16.     friend bool operator<(edge const & a, edge const & b) {
  17.         return a.w < b.w;
  18.     }
  19. };
  20.  
  21. vector<int> parent;
  22.  
  23. int get_p(int a) {
  24.     return (parent[a] == a ? a : parent[a] = get_p(parent[a]));
  25. }
  26.  
  27. bool unite(int a, int b) {
  28.     a = get_p(a);
  29.     b = get_p(b);
  30.  
  31.     if (a == b) return false;
  32.  
  33.     if (rand() % 2) swap(a, b);
  34.     parent[a] = b;
  35.     return true;
  36. }
  37.  
  38.  
  39. void solve() {
  40.     int n, m;
  41.     ll s;
  42.     cin >> n >> m >> s;
  43.  
  44.     parent.resize(n);
  45.     for (int i = 0; i < n; ++i) parent[i] = i;
  46.  
  47.     vector<edge> edges(m);
  48.  
  49.     for (int i = 0; i < m; ++i) {
  50.         int u, v;
  51.         ll w;
  52.         cin >> u >> v >> w;
  53.         edges[i] = edge(u - 1, v - 1, w, i);
  54.     }
  55.  
  56.     sort(edges.begin(), edges.end());
  57.  
  58.     vector<bool> in_mst(m);
  59.     for (auto it = edges.rbegin(); it != edges.rend(); ++it) in_mst[it->pos] = unite(it->u, it->v);
  60.  
  61.     set<int> ans;
  62.     ll cur_s = 0;
  63.     for (auto e : edges)
  64.         if (!in_mst[e.pos])
  65.             if ((cur_s += e.w) <= s)
  66.                 ans.insert(e.pos + 1);
  67.  
  68.     cout << ans.size() << "\n";
  69.     for (int x : ans) cout << x << " ";
  70.  
  71. }
  72.  
  73. int main() {
  74.     ios_base::sync_with_stdio(false);
  75.  
  76.     freopen("destroy.in", "r", stdin);
  77.     freopen("destroy.out", "w", stdout);
  78.  
  79.     solve();
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement