Advertisement
Guest User

Untitled

a guest
May 26th, 2019
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.05 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 111111;
  6.  
  7. int p[maxn], sz[maxn];
  8. int n, m;
  9.  
  10. struct edge {
  11. int u, v, w, id;
  12. bool mst = 0;
  13.  
  14. edge() {}
  15.  
  16. edge(int u, int v, int w) : u(u), v(v), w(w) {}
  17. };
  18.  
  19. edge v[maxn];
  20. set<edge> mst[maxn], non_mst[maxn];
  21.  
  22. bool operator<(edge x, edge y) {
  23. if (x.w != y.w)
  24. return x.w < y.w;
  25. return x.id < y.id;
  26. }
  27.  
  28. bool cmp2(int x, int y) {
  29. return v[x] < v[y];
  30. }
  31.  
  32. int getp(int x) {
  33. if (p[x] == -1)
  34. return x;
  35. return (p[x] = getp(p[x]));
  36. }
  37.  
  38. void merge_sets(int a, int b) {
  39. a = getp(a); b = getp(b);
  40. if (a == b) return;
  41. if (sz[a] < sz[b]) swap(a, b);
  42. if (sz[a] == sz[b]) ++sz[a];
  43. p[b] = a;
  44. }
  45.  
  46. int main() {
  47. cin >> n >> m;
  48. vector<edge> ed(m);
  49. for (int i = 0; i < m; i++) {
  50. cin >> v[i].u >> v[i].v >> v[i].w;
  51. --v[i].u; --v[i].v;
  52. v[i].id = i;
  53. v[i].mst = 0;
  54. ed[i] = v[i];
  55. }
  56. sort(ed.begin(), ed.end());
  57. for (int i = 0; i < n; i++) {
  58. p[i] = -1;
  59. sz[i] = 1;
  60. }
  61. int ans = 0;
  62. for (int i = 0; i < m; i++) {
  63. int a = ed[i].u, b = ed[i].v;
  64. if (getp(a) == getp(b))
  65. continue;
  66. v[ed[i].id].mst = 1;
  67. ans += ed[i].w;
  68. merge_sets(a, b);
  69. }
  70. for (int i = 0; i < m; i++) {
  71. if (v[i].mst) {
  72. mst[v[i].u].insert(v[i]);
  73. mst[v[i].v].insert(v[i]);
  74. } else {
  75. non_mst[v[i].u].insert(v[i]);
  76. non_mst[v[i].v].insert(v[i]);
  77. }
  78. }
  79. int q;
  80. cin >> q;
  81. for (int i = 0; i < q; i++) {
  82. int id;
  83. cin >> id; --id;
  84. if (v[id].u == v[id].v) {
  85. cout << ans << '\n';
  86. continue;
  87. }
  88. if (v[id].mst) {
  89. --v[id].w;
  90. cout << --ans << '\n';
  91. continue;
  92. }
  93. non_mst[v[id].u].erase(v[id]);
  94. non_mst[v[id].v].erase(v[id]);
  95. --v[id].w;
  96. edge g1 = *(mst[v[id].u].rbegin()), g2 = *(mst[v[id].v].rbegin());
  97. if (g1.w > v[id].w) {
  98. v[id].mst = 1;
  99. mst[g1.u].erase(g1);
  100. mst[g1.v].erase(g1);
  101. ans -= g1.w;
  102. ans += v[id].w;
  103. v[g1.id].mst = 0;
  104. non_mst[g1.u].insert(g1);
  105. non_mst[g1.v].insert(g1);
  106. mst[v[id].u].insert(v[id]);
  107. mst[v[id].v].insert(v[id]);
  108. cout << ans << '\n';
  109. continue;
  110. }
  111. if (g2.w > v[id].w) {
  112. v[id].mst = 1;
  113. mst[g2.u].erase(g2);
  114. mst[g2.v].erase(g2);
  115. ans -= g2.w;
  116. ans += v[id].w;
  117. v[g2.id].mst = 0;
  118. non_mst[g2.u].insert(g2);
  119. non_mst[g2.v].insert(g2);
  120. mst[v[id].u].insert(v[id]);
  121. mst[v[id].v].insert(v[id]);
  122. cout << ans << '\n';
  123. continue;
  124. }
  125. non_mst[v[id].u].insert(v[id]);
  126. non_mst[v[id].v].insert(v[id]);
  127. cout << ans << '\n';
  128. }
  129. return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement