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], pr[maxn], cp[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];
- vector<int> g[maxn], cst[maxn];
- bool operator<(edge x, edge y) {
- if (x.w != y.w)
- return x.w < y.w;
- return x.id < y.id;
- }
- bool operator==(edge x, edge y) {
- 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;
- }
- void dfs(int x) {
- for (int i = 0; i < g[x].size(); i++) {
- int to = g[x][i];
- if (to == pr[x])
- continue;
- pr[to] = x;
- cp[to] = cst[x][i];
- dfs(to);
- }
- }
- int acn[11];
- int fuck[11][maxn];
- int find_mst() {
- for (int i = 0; i <= 10; i++)
- acn[i] = 0;
- vector<edge> ed(m);
- for (int i = 0; i < m; i++)
- ed[i] = v[i];
- sort(ed.begin(), ed.end());
- for (int i = 0; i < n; i++) {
- p[i] = -1;
- sz[i] = 1;
- }
- for (int i = 0; i <= 10; i++)
- for (int j = 0; j < n; j++)
- fuck[i][j] = j;
- int ans = 0;
- for (int i = 0; i < m; i++) {
- int a = ed[i].u, b = ed[i].v;
- if (i && ed[i].w != ed[i - 1].w) {
- for (int l = ed[i - 1].w; l < ed[i].w; l++)
- for (int j = 0; j < n; j++)
- fuck[l][j] = getp(j);
- }
- if (getp(a) == getp(b))
- continue;
- ++acn[ed[i].w];
- v[ed[i].id].mst = 1;
- ans += ed[i].w;
- merge_sets(a, b);
- }
- for (int l = ed[m - 1].w; l <= 10; l++)
- for (int j = 0; j < n; j++)
- fuck[l][j] = getp(j);
- return ans;
- }
- int main() {
- map<pair<int, int>, int> mmp;
- cin >> n >> 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;
- }
- int q;
- cin >> q;
- int ans = find_mst();
- for (int i = 0; i < q; i++) {
- int id;
- cin >> id; --id;
- if (v[id].u == v[id].v) {
- cout << ans << '\n';
- continue;
- }
- --v[id].w;
- bool flg = 0;
- for (int j = v[id].w + 1; j <= 10; j++)
- if (acn[j]) {
- flg = 1;
- break;
- }
- if (!flg || fuck[v[id].w][v[id].u] == fuck[v[id].w][v[id].v])
- cout << ans << '\n';
- else
- cout << (ans = find_mst()) << '\n';
- }
- return 0;
- }
- /*
- 8 14
- 1 2 3
- 1 4 3
- 1 5 8
- 1 8 2
- 2 3 5
- 2 5 3
- 3 6 1
- 3 7 2
- 3 8 6
- 4 6 6
- 4 7 7
- 5 7 3
- 5 7 7
- 6 8 2
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement