fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Dùng long long cho tổng trọng số MST để tránh tràn số
  5. typedef long long ll;
  6. const int INF = 1e9;
  7.  
  8. // Cấu trúc Disjoint Set Union (DSU) tiêu chuẩn
  9. // Hỗ trợ nén đường đi (path compression) và gộp theo kích thước (union by size)
  10. struct DSU {
  11.     vector<int> parent;
  12.     vector<int> sz; // Kích thước của thành phần liên thông
  13.  
  14.     DSU(int n) {
  15.         parent.resize(n);
  16.         sz.resize(n);
  17.         reset(n);
  18.     }
  19.  
  20.     void reset(int n) {
  21.         for(int i = 0; i < n; i++) {
  22.             parent[i] = i;
  23.             sz[i] = 1;
  24.         }
  25.     }
  26.  
  27.     int find(int u) {
  28.         if (u == parent[u]) return u;
  29.         return parent[u] = find(parent[u]); // Path compression
  30.     }
  31.  
  32.     // Trả về true nếu gộp thành công (tức là u và v chưa liên thông trước đó)
  33.     bool unite(int u, int v) {
  34.         u = find(u);
  35.         v = find(v);
  36.         if (u != v) {
  37.             if (sz[u] < sz[v]) swap(u, v);
  38.             parent[v] = u;
  39.             sz[u] += sz[v];
  40.             return true;
  41.         }
  42.         return false;
  43.     }
  44. };
  45.  
  46. struct DynamicMST {
  47.     struct Edge {
  48.         int u, v, w;
  49.         int time_start, time_end; // Khoảng thời gian [L, R] mà cạnh này tồn tại/có trọng số w
  50.  
  51.         // Sắp xếp cạnh theo trọng số tăng dần (để chạy Kruskal)
  52.         bool operator<(const Edge& other) const {
  53.             return w < other.w;
  54.         }
  55.     };
  56.  
  57.     vector<Edge> all_edges;         // Danh sách tất cả các phiên bản của cạnh theo thời gian
  58.     vector<array<int, 3>> init_edges; // Trạng thái ban đầu của các cạnh
  59.     vector<int> last_touched;       // Thời điểm cuối cùng cạnh i được cập nhật
  60.     int num_nodes;
  61.     int current_query_time = 0;
  62.  
  63.     // Hai DSU dùng cho 2 mục đích khác nhau trong thuật toán
  64.     DSU dsu_temp, dsu_contract; 
  65.     vector<int> node_mapping; // Dùng để đánh số lại đỉnh sau khi co (contract)
  66.     vector<ll> results;       // Lưu kết quả MST tại mỗi thời điểm
  67.  
  68.     DynamicMST(vector<array<int, 3>> edges, int n) 
  69.         : init_edges(edges), last_touched(edges.size()), num_nodes(n), 
  70.           dsu_temp(n), dsu_contract(n), node_mapping(n) {
  71.         // Khởi tạo thời điểm last_touched của mọi cạnh là 0
  72.     }
  73.  
  74.     // Hàm cập nhật trọng số cạnh thứ edge_idx thành weight_new
  75.     void update(int edge_idx, int weight_new) {
  76.         current_query_time++;
  77.         auto& [u, v, w_old] = init_edges[edge_idx];
  78.  
  79.         // Tạo một phiên bản cạnh tồn tại từ lần sửa cuối đến hiện tại
  80.         all_edges.push_back({u, v, w_old, last_touched[edge_idx], current_query_time});
  81.  
  82.         // Cập nhật thông tin mới
  83.         last_touched[edge_idx] = current_query_time;
  84.         w_old = weight_new; // Lưu trọng số mới vào mảng gốc để dùng cho lần update sau
  85.     }
  86.  
  87.     // Hàm chính thực hiện thuật toán
  88.     vector<ll> run() {
  89.         int m = init_edges.size();
  90.         current_query_time++;
  91.  
  92.         // Đẩy nốt các phiên bản cuối cùng của cạnh (tồn tại đến hết thời gian)
  93.         for(int i = 0; i < m; ++i) {
  94.             auto& [u, v, w] = init_edges[i];
  95.             all_edges.push_back({u, v, w, last_touched[i], current_query_time});
  96.         }
  97.  
  98.         // Sắp xếp tất cả các cạnh theo trọng số ngay từ đầu
  99.         // Điều này giúp ta không phải sort lại trong đệ quy (tối ưu logN)
  100.         sort(all_edges.begin(), all_edges.end());
  101.  
  102.         results.resize(current_query_time);
  103.  
  104.         // Gọi đệ quy giải quyết đoạn thời gian [0, Q]
  105.         solve(0, current_query_time, all_edges, num_nodes, 0);
  106.  
  107.         return results;
  108.     }
  109.  
  110.     // Hàm đệ quy chia để trị: Xử lý đoạn thời gian [l, r]
  111.     // current_edges: Danh sách cạnh tiềm năng
  112.     // n: Số lượng đỉnh hiện tại (sau khi đã co bớt)
  113.     // current_mst_sum: Tổng trọng số các cạnh đã chắc chắn thuộc MST (bị co lại)
  114.     void solve(int l, int r, vector<Edge>& edges, int n, ll current_mst_sum) {
  115.  
  116.         // 1. Lọc cạnh (Filter): Chỉ giữ lại các cạnh có tồn tại trong khoảng [l, r]
  117.         // Dùng stable_partition để đẩy các cạnh hợp lệ lên đầu mà KHÔNG làm mất thứ tự trọng số
  118.         auto it = stable_partition(edges.begin(), edges.end(), [&](const Edge& e) {
  119.             // Giữ lại nếu khoảng thời gian của cạnh giao với [l, r]
  120.             return !(e.time_end <= l || r <= e.time_start);
  121.         });
  122.         edges.erase(it, edges.end()); // Xóa các cạnh không liên quan
  123.  
  124.         // Base case: Nếu l + 1 == r (đã đến 1 truy vấn cụ thể)
  125.         if (l + 1 == r) {
  126.             // Lúc này số lượng đỉnh n rất nhỏ, các cạnh đã lọc cũng rất ít
  127.             // Ta chạy Kruskal bình thường để tính nốt phần còn lại
  128.             dsu_temp.reset(n);
  129.             for (auto& e : edges) {
  130.                 // Chỉ xét các cạnh bao trùm thời điểm này
  131.                 if (e.time_start <= l && r <= e.time_end) {
  132.                     if (dsu_temp.unite(e.u, e.v)) {
  133.                         current_mst_sum += e.w;
  134.                     }
  135.                 }
  136.             }
  137.             results[l] = current_mst_sum;
  138.             return;
  139.         }
  140.  
  141.         // --- BƯỚC 2: CONTRACTION (Co đỉnh) ---
  142.         // Mục tiêu: Tìm các cạnh TĨNH chắc chắn thuộc MST và co chúng lại.
  143.  
  144.         dsu_temp.reset(n);     // DSU dùng để check liên thông
  145.         dsu_contract.reset(n); // DSU dùng để lưu các đỉnh sẽ bị co
  146.  
  147.         // 2a. Nối tất cả các cạnh ĐỘNG (Active edges - cạnh bị thay đổi trong [l, r])
  148.         // Ta coi như chúng có trọng số -vô cùng để ưu tiên nối trước.
  149.         for (auto& e : edges) {
  150.             if (l < e.time_start || e.time_end < r) { // Điều kiện cạnh động
  151.                 dsu_temp.unite(e.u, e.v);
  152.             }
  153.         }
  154.  
  155.         // 2b. Duyệt các cạnh TĨNH (Static edges - bao trùm cả [l, r])
  156.         // Vì edges đã sort theo w, nên ta đang xét từ nhẹ đến nặng.
  157.         for (auto& e : edges) {
  158.             if (e.time_start <= l && r <= e.time_end) { // Cạnh tĩnh
  159.                 // Nếu cạnh tĩnh nối 2 thành phần mà ngay cả tất cả cạnh động cũng chưa nối được
  160.                 // => Cạnh này BẮT BUỘC phải có trong MST.
  161.                 if (dsu_temp.unite(e.u, e.v)) {
  162.                     dsu_contract.unite(e.u, e.v); // Đánh dấu để lát nữa co đỉnh
  163.                     current_mst_sum += e.w;       // Cộng luôn vào kết quả
  164.                 }
  165.             }
  166.         }
  167.  
  168.         // --- BƯỚC 3: RELABELING (Đánh số lại đỉnh) ---
  169.         // Biến đồ thị to thành đồ thị nhỏ hơn dựa trên dsu_contract
  170.         int new_nodes_count = 0;
  171.         vector<int> component_id(n); // Mapping từ đỉnh cũ -> đỉnh mới
  172.  
  173.         // Mỗi thành phần liên thông trong dsu_contract sẽ thành 1 đỉnh mới
  174.         for (int i = 0; i < n; ++i) {
  175.             if (dsu_contract.find(i) == i) {
  176.                 component_id[i] = new_nodes_count++;
  177.             }
  178.         }
  179.         // Gán ID cho các đỉnh con
  180.         for (int i = 0; i < n; ++i) {
  181.             node_mapping[i] = component_id[dsu_contract.find(i)];
  182.         }
  183.  
  184.         // --- BƯỚC 4: REDUCTION (Loại bỏ cạnh thừa) ---
  185.         // Mục tiêu: Loại bỏ các cạnh TĨNH tạo thành chu trình với các cạnh tĩnh tốt hơn.
  186.  
  187.         // Cập nhật lại đỉnh u, v cho tất cả các cạnh theo ID mới
  188.         // Đồng thời check xem cạnh nào trở nên vô dụng (tự nối chính nó hoặc tạo chu trình)
  189.  
  190.         dsu_temp.reset(new_nodes_count); // Reset DSU cho đồ thị mới (đã co)
  191.  
  192.         // Ta cần duyệt lại edges để lọc. 
  193.         // Logic: Các cạnh tĩnh đã co (ở bước 2) giờ thành khuyên (loop) u==v -> bỏ qua.
  194.         // Các cạnh tĩnh khác: Nếu tạo chu trình trong đồ thị mới -> bỏ qua (vì có cạnh khác tốt hơn thay thế rồi).
  195.  
  196.         // Lưu ý: Code gốc thực hiện check reduction ngay trong lúc relabel
  197.         for (auto& e : edges) {
  198.             // Map u, v sang đỉnh mới
  199.             e.u = node_mapping[e.u];
  200.             e.v = node_mapping[e.v];
  201.  
  202.             if (e.time_start <= l && r <= e.time_end) { // Với cạnh tĩnh
  203.                 // Nếu 2 đầu mút trùng nhau (do đã bị co) -> Bỏ qua
  204.                 // Nếu nối 2 đỉnh đã liên thông (tạo chu trình trong đồ thị mới) -> Bỏ qua
  205.                 if (!dsu_temp.unite(e.u, e.v)) {
  206.                     // Đánh dấu cạnh này là vô dụng bằng cách gán khoảng thời gian phi lý
  207.                     // Nó sẽ bị xóa ở lệnh erase trong tầng đệ quy tiếp theo
  208.                     e.time_start = INF; 
  209.                     e.time_end = -INF;
  210.                 }
  211.             }
  212.         }
  213.  
  214.         // --- BƯỚC 5: ĐỆ QUY ---
  215.         int mid = (l + r) / 2;
  216.         solve(l, mid, edges, new_nodes_count, current_mst_sum);
  217.         solve(mid, r, edges, new_nodes_count, current_mst_sum);
  218.     }
  219. };
  220.  
  221. int main() {
  222.     ios_base::sync_with_stdio(false);
  223.     cin.tie(NULL);
  224.  
  225.     int n, m, q;
  226.     if (!(cin >> n >> m >> q)) return 0;
  227.  
  228.     vector<array<int, 3>> edges(m);
  229.     for (auto& [u, v, w] : edges) {
  230.         cin >> u >> v >> w;
  231.         --u; --v; // Chuyển về 0-based index
  232.     }
  233.  
  234.     DynamicMST mst_solver(edges, n);
  235.  
  236.     for (int i = 0; i < q; ++i) {
  237.         int k, d;
  238.         cin >> k >> d;
  239.         --k; // 0-based index cho chỉ số cạnh
  240.         mst_solver.update(k, d);
  241.     }
  242.  
  243.     auto answers = mst_solver.run();
  244.  
  245.     // In kết quả từ 1 đến q (bỏ qua trạng thái 0 nếu đề bài không hỏi)
  246.     for (int i = 1; i <= q; ++i) {
  247.         cout << answers[i] << '\n';
  248.     }
  249.  
  250.     return 0;
  251. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lVhnsV
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!