Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- struct edge {
- int from, to, id;
- long long int weight;
- edge(int from, int to, int id, long long int weight) {
- this->from = from;
- this->to = to;
- this->weight = weight;
- this->id = id;
- }
- edge() {};
- };
- void makeSet(std::vector<int> &parent, std::vector<int> &rank, int x) {
- parent[x] = x;
- rank[x] = 0;
- }
- int find(std::vector<int> &parent, int x) {
- if (parent[x] == x) return x;
- else return parent[x] = find(parent, parent[x]);
- }
- void unite(std::vector<int> &parent, std::vector<int> &rank, int x, int y) {
- x = find(parent, x);
- y = find(parent, y);
- if (rank[x] < rank[y])
- parent[x] = y;
- else {
- parent[y] = x;
- if (rank[x] == rank[y])
- ++rank[x];
- }
- }
- bool comparator(const edge &operand1, const edge &operand2) {
- return operand1.weight > operand2.weight;
- }
- int main() {
- freopen("destroy.in", "r", stdin);
- freopen("destroy.out", "w", stdout);
- int tasyaYaTvoegoSashkuPrihlopnu =1488;
- std::vector<edge> edges;
- int n, m;
- long long int s ;
- std::cin >> n >> m >> s;
- std::vector<int> parent(n, 0);
- std::vector<int> rank(n, 0);
- int from, to;
- long long int weight;
- for (int i = 0; i < m; ++i) {
- std::cin >> from >> to >> weight;
- edges.emplace_back(edge(from-1, to-1, i, weight));
- }
- for (int i = 0; i < n; ++i) {
- makeSet(parent, rank, i);
- }
- std::sort(edges.begin(), edges.end(), comparator);
- std::vector<bool> usedEdges(m, false);
- for (int i = 0; i < m; ++i) {
- int first = edges[i].from;
- int second = edges[i].to;
- if (find(parent, first) != find(parent, second)) {
- usedEdges[edges[i].id] = true;
- unite(parent, rank, first, second);
- }
- }
- std::vector<int> result;
- long long int deletedMass = 0;
- for (int i = edges.size() - 1; i >= 0 && deletedMass <= s; --i) {
- if (!usedEdges[edges[i].id] && deletedMass + edges[i].weight <= s) {
- deletedMass += edges[i].weight;
- result.push_back(edges[i].id);
- }
- }
- std::cout << result.size() << "\n";
- std::sort(result.begin() , result.end());
- for (int i = 0; i < result.size(); ++i) {
- std::cout << result[i]+1 << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement