Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct edge {
  6. int from, to, id;
  7. long long int weight;
  8.  
  9. edge(int from, int to, int id, long long int weight) {
  10. this->from = from;
  11. this->to = to;
  12. this->weight = weight;
  13. this->id = id;
  14. }
  15. edge() {};
  16. };
  17.  
  18. void makeSet(std::vector<int> &parent, std::vector<int> &rank, int x) {
  19. parent[x] = x;
  20. rank[x] = 0;
  21. }
  22.  
  23. int find(std::vector<int> &parent, int x) {
  24. if (parent[x] == x) return x;
  25. else return parent[x] = find(parent, parent[x]);
  26. }
  27.  
  28. void unite(std::vector<int> &parent, std::vector<int> &rank, int x, int y) {
  29. x = find(parent, x);
  30. y = find(parent, y);
  31. if (rank[x] < rank[y])
  32. parent[x] = y;
  33. else {
  34. parent[y] = x;
  35. if (rank[x] == rank[y])
  36. ++rank[x];
  37. }
  38. }
  39.  
  40. bool comparator(const edge &operand1, const edge &operand2) {
  41. return operand1.weight > operand2.weight;
  42. }
  43.  
  44.  
  45. int main() {
  46. freopen("destroy.in", "r", stdin);
  47. freopen("destroy.out", "w", stdout);
  48. int tasyaYaTvoegoSashkuPrihlopnu =1488;
  49. std::vector<edge> edges;
  50. int n, m;
  51. long long int s ;
  52. std::cin >> n >> m >> s;
  53. std::vector<int> parent(n, 0);
  54. std::vector<int> rank(n, 0);
  55. int from, to;
  56. long long int weight;
  57. for (int i = 0; i < m; ++i) {
  58. std::cin >> from >> to >> weight;
  59. edges.emplace_back(edge(from-1, to-1, i, weight));
  60. }
  61. for (int i = 0; i < n; ++i) {
  62. makeSet(parent, rank, i);
  63. }
  64. std::sort(edges.begin(), edges.end(), comparator);
  65. std::vector<bool> usedEdges(m, false);
  66. for (int i = 0; i < m; ++i) {
  67. int first = edges[i].from;
  68. int second = edges[i].to;
  69. if (find(parent, first) != find(parent, second)) {
  70. usedEdges[edges[i].id] = true;
  71. unite(parent, rank, first, second);
  72. }
  73. }
  74. std::vector<int> result;
  75. long long int deletedMass = 0;
  76. for (int i = edges.size() - 1; i >= 0 && deletedMass <= s; --i) {
  77. if (!usedEdges[edges[i].id] && deletedMass + edges[i].weight <= s) {
  78. deletedMass += edges[i].weight;
  79. result.push_back(edges[i].id);
  80. }
  81. }
  82. std::cout << result.size() << "\n";
  83. std::sort(result.begin() , result.end());
  84. for (int i = 0; i < result.size(); ++i) {
  85. std::cout << result[i]+1 << " ";
  86. }
  87.  
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement