Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- struct edge {
- int u, v, pos;
- ll w;
- edge() = default;
- edge(int _u, int _v, ll _w, int _pos) {
- u = _u, v = _v, w = _w, pos = _pos;
- }
- friend bool operator<(edge const & a, edge const & b) {
- return a.w < b.w;
- }
- };
- vector<int> parent;
- int get_p(int a) {
- return (parent[a] == a ? a : parent[a] = get_p(parent[a]));
- }
- bool unite(int a, int b) {
- a = get_p(a);
- b = get_p(b);
- if (a == b) return false;
- if (rand() % 2) swap(a, b);
- parent[a] = b;
- return true;
- }
- void solve() {
- int n, m;
- ll s;
- cin >> n >> m >> s;
- parent.resize(n);
- for (int i = 0; i < n; ++i) parent[i] = i;
- vector<edge> edges(m);
- for (int i = 0; i < m; ++i) {
- int u, v;
- ll w;
- cin >> u >> v >> w;
- edges[i] = edge(u - 1, v - 1, w, i);
- }
- sort(edges.begin(), edges.end());
- vector<bool> in_mst(m);
- for (auto it = edges.rbegin(); it != edges.rend(); ++it) in_mst[it->pos] = unite(it->u, it->v);
- set<int> ans;
- ll cur_s = 0;
- for (auto e : edges)
- if (!in_mst[e.pos])
- if ((cur_s += e.w) <= s)
- ans.insert(e.pos + 1);
- cout << ans.size() << "\n";
- for (int x : ans) cout << x << " ";
- }
- int main() {
- ios_base::sync_with_stdio(false);
- freopen("destroy.in", "r", stdin);
- freopen("destroy.out", "w", stdout);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement