Bình luận

• 
  

  20

  

  tronglee  đã bình luận lúc 6, Tháng 10, 2025, 12:52

  Spoil !!!

  Bước 1: Phân tích bài toán

  • Có N thành phố và M con đường có thể xây, mỗi con đường (u, v) có chi phí w.
  • Cần xây dựng hệ thống sao cho mọi thành phố được cấp điện với tổng chi phí nhỏ nhất.
  • Đây là bài toán cây khung nhỏ nhất (Minimum Spanning Tree - MST).

  Bước 2: Ý tưởng chính

  • Gọi chi phí của cây khung nhỏ nhất là kq.
  • Với mỗi truy vấn (A, B) — hai trạm điện đặt tại A, B:
    • Nếu ta loại bỏ cạnh lớn nhất trên đường đi A ↔ B trong MST,
    • Hai cây con tương ứng chính là hai vùng có trạm phát điện.
    • Khi đó chi phí tối thiểu = kq - max_edge(A, B).

  Bước 3: Các bước thực hiện

  1️⃣ Tạo cây khung nhỏ nhất (Kruskal)

  • Dùng DSU để nối các đỉnh theo cạnh nhỏ nhất.

  2️⃣ Tiền xử lý LCA

  • dp[u][j]: tổ tiên thứ 2^j của u.
  • w[u][j]: trọng số lớn nhất trên đoạn u đến dp[u][j].

  3️⃣ Trả lời truy vấn

  • Dùng LCA tìm cạnh lớn nhất trên đường A–B.
  • Kết quả = kq - max_edge(A, B).

  Bước 4: Độ phức tạp

  • Kruskal: O(M log M)
  • Tiền xử lý LCA: O(N log N)
  • Mỗi truy vấn: O(log N)

  Tổng thể: đủ nhanh với N ≤ 4000, M ≤ 400000, Q ≤ 200000.

  Bước 5: Mã nguồn tham khảo

  #include <bits/stdc++.h>
  #define int long long
  #define pii pair<int,int>
  using namespace std;
  
  const int N = 4005, M = 400005;
  struct Edge {
      int u, v, w;
      bool operator < (const Edge &o) const { return w < o.w; }
  };
  
  int n, m, q, kq = 0;
  Edge E[M];
  vector<pii> ke[N];
  int parent[N], sz[N], h[N], dp[N][20], wmax[N][20], g[N];
  
  int Find(int u){ return u == parent[u] ? u : parent[u] = Find(parent[u]); }
  void Union(int u, int v){ if(sz[u]<sz[v]) swap(u,v); parent[v]=u; sz[u]+=sz[v]; }
  
  void Kruskal(){
      for(int i=1;i<=n;i++) parent[i]=i, sz[i]=1;
      sort(E+1,E+1+m);
      for(int i=1;i<=m;i++){
          int u=Find(E[i].u), v=Find(E[i].v);
          if(u!=v){
              kq+=E[i].w;
              Union(u,v);
              ke[E[i].u].push_back({E[i].v,E[i].w});
              ke[E[i].v].push_back({E[i].u,E[i].w});
          }
      }
  }
  
  void DFS(int u, int p){
      for(auto [v, w]: ke[u]) if(v!=p){
          g[v]=u; h[v]=h[u]+1; wmax[v][0]=w;
          DFS(v,u);
      }
  }
  
  void Build(){
      for(int i=1;i<=n;i++) dp[i][0]=g[i];
      for(int j=1;(1<<j)<=n;j++)
          for(int i=1;i<=n;i++)
              dp[i][j]=dp[dp[i][j-1]][j-1],
              wmax[i][j]=max(wmax[i][j-1], wmax[dp[i][j-1]][j-1]);
  }
  
  int LCAmax(int u,int v){
      if(h[u]<h[v]) swap(u,v);
      int res=0, diff=h[u]-h[v];
      for(int i=19;i>=0;i--) if(diff>>i&1)
          res=max(res,wmax[u][i]), u=dp[u][i];
      if(u==v) return res;
      for(int i=19;i>=0;i--) if(dp[u][i]!=dp[v][i]){
          res=max({res,wmax[u][i],wmax[v][i]});
          u=dp[u][i], v=dp[v][i];
      }
      return max({res,wmax[u][0],wmax[v][0]});
  }
  
  signed main(){
      ios::sync_with_stdio(0); cin.tie(0);
      cin>>n>>m;
      for(int i=1;i<=m;i++) cin>>E[i].u>>E[i].v>>E[i].w;
      Kruskal(); DFS(1,1); Build();
      cin>>q;
      while(q--){
          int a,b; cin>>a>>b;
          cout<<kq - LCAmax(a,b)<<"\n";
      }
  }
  

  Bước 6: Tóm tắt nhanh

  • Xây MST bằng Kruskal.
  • Tiền xử lý LCA để tìm cạnh lớn nhất trên đường A–B.
  • Mỗi truy vấn: kq - max_edge(A, B).
  • Mỗi truy vấn chỉ O(log N), rất nhanh.

• 
  

  -7

  

  hoabanmatuyaccclone  đã bình luận lúc 27, Tháng 10, 2023, 17:29

  bài khó vl

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.