Advertisement
Guest User

Untitled

a guest
May 26th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.97 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], pr[maxn], cp[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. vector<int> g[maxn], cst[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 operator==(edge x, edge y) {
  29. return x.id == y.id;
  30. }
  31.  
  32. bool cmp2(int x, int y) {
  33. return v[x] < v[y];
  34. }
  35.  
  36. int getp(int x) {
  37. if (p[x] == -1)
  38. return x;
  39. return (p[x] = getp(p[x]));
  40. }
  41.  
  42. void merge_sets(int a, int b) {
  43. a = getp(a); b = getp(b);
  44. if (a == b) return;
  45. if (sz[a] < sz[b]) swap(a, b);
  46. if (sz[a] == sz[b]) ++sz[a];
  47. p[b] = a;
  48. }
  49.  
  50. void dfs(int x) {
  51. for (int i = 0; i < g[x].size(); i++) {
  52. int to = g[x][i];
  53. if (to == pr[x])
  54. continue;
  55. pr[to] = x;
  56. cp[to] = cst[x][i];
  57. dfs(to);
  58. }
  59. }
  60.  
  61. int acn[11];
  62. int fuck[11][maxn];
  63.  
  64. int find_mst() {
  65. for (int i = 0; i <= 10; i++)
  66. acn[i] = 0;
  67. vector<edge> ed(m);
  68. for (int i = 0; i < m; i++)
  69. ed[i] = v[i];
  70. sort(ed.begin(), ed.end());
  71. for (int i = 0; i < n; i++) {
  72. p[i] = -1;
  73. sz[i] = 1;
  74. }
  75. for (int i = 0; i <= 10; i++)
  76. for (int j = 0; j < n; j++)
  77. fuck[i][j] = j;
  78. int ans = 0;
  79. for (int i = 0; i < m; i++) {
  80. int a = ed[i].u, b = ed[i].v;
  81. if (i && ed[i].w != ed[i - 1].w) {
  82. for (int l = ed[i - 1].w; l < ed[i].w; l++)
  83. for (int j = 0; j < n; j++)
  84. fuck[l][j] = getp(j);
  85. }
  86. if (getp(a) == getp(b))
  87. continue;
  88. ++acn[ed[i].w];
  89. v[ed[i].id].mst = 1;
  90. ans += ed[i].w;
  91. merge_sets(a, b);
  92. }
  93. for (int l = ed[m - 1].w; l <= 10; l++)
  94. for (int j = 0; j < n; j++)
  95. fuck[l][j] = getp(j);
  96. return ans;
  97. }
  98.  
  99. int main() {
  100. map<pair<int, int>, int> mmp;
  101. cin >> n >> m;
  102. for (int i = 0; i < m; i++) {
  103. cin >> v[i].u >> v[i].v >> v[i].w;
  104. --v[i].u; --v[i].v;
  105. v[i].id = i;
  106. v[i].mst = 0;
  107. }
  108. int q;
  109. cin >> q;
  110. int ans = find_mst();
  111. for (int i = 0; i < q; i++) {
  112. int id;
  113. cin >> id; --id;
  114. if (v[id].u == v[id].v) {
  115. cout << ans << '\n';
  116. continue;
  117. }
  118. --v[id].w;
  119. bool flg = 0;
  120. for (int j = v[id].w + 1; j <= 10; j++)
  121. if (acn[j]) {
  122. flg = 1;
  123. break;
  124. }
  125. if (!flg || fuck[v[id].w][v[id].u] == fuck[v[id].w][v[id].v])
  126. cout << ans << '\n';
  127. else
  128. cout << (ans = find_mst()) << '\n';
  129. }
  130. return 0;
  131. }
  132. /*
  133. 8 14
  134. 1 2 3
  135. 1 4 3
  136. 1 5 8
  137. 1 8 2
  138. 2 3 5
  139. 2 5 3
  140. 3 6 1
  141. 3 7 2
  142. 3 8 6
  143. 4 6 6
  144. 4 7 7
  145. 5 7 3
  146. 5 7 7
  147. 6 8 2
  148.  
  149. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement