Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <string>
- #include <cstring>
- #include <queue>
- #include <iostream>
- #include <fstream>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- int nextInt() {
- int x;
- scanf("%d", &x);
- return x;
- }
- char inp[10000];
- string nextString() {
- scanf("%s", inp);
- return inp;
- }
- double nextDouble() {
- double x;
- scanf("%lf", &x);
- return x;
- }
- struct Edge {
- int from;
- int to;
- int cost;
- bool inSpaningTree;
- } edges[81000];
- int edgesCount = 0;
- void addEdge(vector<vector<int> > &adj, int x, int y, int cost) {
- edges[edgesCount].from = x;
- edges[edgesCount].to = y;
- edges[edgesCount].cost = cost;
- adj[x].push_back(edgesCount++);
- edges[edgesCount].from = y;
- edges[edgesCount].to = x;
- edges[edgesCount].cost = cost;
- adj[y].push_back(edgesCount++);
- }
- bool edgeLess(int i, int j) {
- Edge &a = edges[i];
- Edge &b = edges[j];
- return a.cost < b.cost;
- }
- int parent[41000];
- int Find(int x) {
- if (parent[x] == x) {
- return x;
- }
- return parent[x] = Find(parent[x]);
- }
- bool Union(int x, int y) {
- x = Find(x);
- y = Find(y);
- if (x == y) {
- return false;
- }
- if (rand() % 2) {
- swap(x, y);
- }
- parent[x] = y;
- return true;
- }
- void AddEdgeToTree(vector<vector<int> > &tree, int id) {
- tree[edges[id].from].push_back(id);
- edges[id].inSpaningTree = true;
- }
- int used[41000];
- void Erase(vector<int> &a, int x) {
- edges[x].inSpaningTree = false;
- a.erase(find(a.begin(), a.end(), x));
- }
- void dfsMark(int v, vector<vector<int> > &tree, int usedVal) {
- used[v] = usedVal;
- for (int i = 0; i < tree[v].size(); ++i) {
- int u = edges[tree[v][i]].to;
- if (used[u] != usedVal) {
- dfsMark(u, tree, usedVal);
- }
- }
- }
- int bestCost, bestId;
- void dfsFindEdge(int v, vector<vector<int> > &tree, vector<vector<int> > &adj, int usedVal) {
- used[v] = -usedVal;
- for (int i = 0; i < adj[v].size(); ++i) {
- int id = adj[v][i];
- Edge &e = edges[id];
- if (e.cost < bestCost) {
- bestCost = e.cost;
- bestId = id;
- }
- }
- for (int i = 0; i < tree[v].size(); ++i) {
- int u = edges[tree[v][i]].to;
- if (used[u] == usedVal) {
- dfsMark(u, tree, usedVal);
- }
- }
- }
- void dfsBiggestEdge(int v, int to, vector<vector<int> > &tree, int usedVal, int curMax, int curId) {
- if (v == to) {
- if (curMax > bestCost) {
- bestCost = curMax;
- bestId = curId;
- }
- return;
- }
- used[v] = usedVal;
- for (int i = 0; i < tree[v].size(); ++i) {
- int id = tree[v][i];
- int u = edges[id].to;
- if (used[u] != usedVal) {
- int newMax = curMax;
- int newId = curId;
- if (edges[id].cost > newMax) {
- newMax = edges[id].cost;
- newId = id;
- }
- dfsBiggestEdge(u, to, tree, usedVal, newMax, newId);
- }
- }
- }
- int main() {
- int n = nextInt();
- int m = nextInt();
- vector<vector<int> > adj(n);
- vector<vector<int> > tree(n);
- for (int i = 0; i < m; ++i) {
- int x = nextInt() - 1;
- int y = nextInt() - 1;
- int cost = nextInt();
- addEdge(adj, x, y, cost);
- }
- for (int i = 0; i < n; ++i) {
- parent[i] = i;
- }
- vector<int> order(m * 2);
- for (int i = 0; i < order.size(); ++i) {
- order[i] = i;
- }
- sort(order.begin(), order.end(), edgeLess);
- int totalCost = 0;
- for (int t = 0; t < order.size(); ++t) {
- int i = order[t];
- int x = edges[i].from;
- int y = edges[i].to;
- if (Union(x, y)) {
- AddEdgeToTree(tree, i);
- AddEdgeToTree(tree, i ^ 1);
- totalCost += edges[i].cost;
- }
- }
- memset(used, -1, sizeof(used));
- int q = nextInt();
- while (q--) {
- int id = 2 * (nextInt() - 1);
- int newCost = nextInt();
- if (rand() % 2) {
- id ^= 1;
- }
- int x = edges[id].from;
- int y = edges[id].to;
- if (edges[id].inSpaningTree) {
- totalCost -= edges[id].cost;
- Erase(tree[x], id);
- Erase(tree[y], id ^ 1);
- edges[id].cost = newCost;
- edges[id ^ 1].cost = newCost;
- dfsMark(y, tree, q + 1);
- bestCost = 1000000;
- dfsFindEdge(y, tree, adj, q + 1);
- AddEdgeToTree(tree, bestId);
- AddEdgeToTree(tree, bestId ^ 1);
- totalCost += edges[bestId].cost;
- } else {
- edges[id].cost = newCost;
- edges[id ^ 1].cost = newCost;
- bestCost = -1;
- dfsBiggestEdge(x, y, tree, q + 1, -1, -1);
- if (bestCost > newCost) {
- totalCost -= bestCost;
- Erase(tree[edges[bestId].from], bestId);
- Erase(tree[edges[bestId ^ 1].from], bestId ^ 1);
- AddEdgeToTree(tree, id);
- AddEdgeToTree(tree, id ^ 1);
- totalCost += edges[id].cost;
- }
- }
- printf("%d\n", totalCost);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement