Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 111111;
- int p[maxn], sz[maxn];
- int n, m;
- struct edge {
- int u, v, w, id;
- bool mst = 0;
- edge() {}
- edge(int u, int v, int w) : u(u), v(v), w(w) {}
- };
- edge v[maxn];
- set<edge> mst[maxn], non_mst[maxn];
- bool operator<(edge x, edge y) {
- if (x.w != y.w)
- return x.w < y.w;
- return x.id < y.id;
- }
- bool cmp2(int x, int y) {
- return v[x] < v[y];
- }
- int getp(int x) {
- if (p[x] == -1)
- return x;
- return (p[x] = getp(p[x]));
- }
- void merge_sets(int a, int b) {
- a = getp(a); b = getp(b);
- if (a == b) return;
- if (sz[a] < sz[b]) swap(a, b);
- if (sz[a] == sz[b]) ++sz[a];
- p[b] = a;
- }
- int main() {
- cin >> n >> m;
- vector<edge> ed(m);
- for (int i = 0; i < m; i++) {
- cin >> v[i].u >> v[i].v >> v[i].w;
- --v[i].u; --v[i].v;
- v[i].id = i;
- v[i].mst = 0;
- ed[i] = v[i];
- }
- sort(ed.begin(), ed.end());
- for (int i = 0; i < n; i++) {
- p[i] = -1;
- sz[i] = 1;
- }
- int ans = 0;
- for (int i = 0; i < m; i++) {
- int a = ed[i].u, b = ed[i].v;
- if (getp(a) == getp(b))
- continue;
- v[ed[i].id].mst = 1;
- ans += ed[i].w;
- merge_sets(a, b);
- }
- for (int i = 0; i < m; i++) {
- if (v[i].mst) {
- mst[v[i].u].insert(v[i]);
- mst[v[i].v].insert(v[i]);
- } else {
- non_mst[v[i].u].insert(v[i]);
- non_mst[v[i].v].insert(v[i]);
- }
- }
- int q;
- cin >> q;
- for (int i = 0; i < q; i++) {
- int id;
- cin >> id; --id;
- if (v[id].mst) {
- --v[id].w;
- cout << --ans << '\n';
- continue;
- }
- non_mst[v[id].u].erase(v[id]);
- non_mst[v[id].v].erase(v[id]);
- --v[id].w;
- edge g1 = *(mst[v[id].u].rbegin()), g2 = *(mst[v[id].v].rbegin());
- if (g1.w > v[id].w) {
- v[id].mst = 1;
- mst[g1.u].erase(g1);
- mst[g1.v].erase(g1);
- ans -= g1.w;
- ans += v[id].w;
- v[g1.id].mst = 0;
- non_mst[g1.u].insert(g1);
- non_mst[g1.v].insert(g1);
- mst[v[id].u].insert(v[id]);
- mst[v[id].v].insert(v[id]);
- cout << ans << '\n';
- continue;
- }
- if (g2.w > v[id].w) {
- v[id].mst = 1;
- mst[g2.u].erase(g2);
- mst[g2.v].erase(g2);
- ans -= g2.w;
- ans += v[id].w;
- v[g2.id].mst = 0;
- non_mst[g2.u].insert(g2);
- non_mst[g2.v].insert(g2);
- mst[v[id].u].insert(v[id]);
- mst[v[id].v].insert(v[id]);
- cout << ans << '\n';
- continue;
- }
- non_mst[v[id].u].insert(v[id]);
- non_mst[v[id].v].insert(v[id]);
- cout << ans << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement