fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <numeric>
  6. using namespace std;
  7.  
  8. // Struct đại diện cho một cạnh trong đồ thị
  9. struct Edge {
  10.     int u, v, c; // u và v là 2 đỉnh của cạnh, c là chi phí
  11.     bool operator<(const Edge& other) const { // So sánh các cạnh theo chi phí
  12.         return c < other.c;
  13.     }
  14. };
  15.  
  16. // Struct cho Union-Find (Disjoint Set Union)
  17. struct UnionFind {
  18.     vector<int> parent, rank; // parent[i] là cha của đỉnh i, rank[i] là độ cao của cây tại đỉnh i
  19.  
  20.     UnionFind(int n) {
  21.         parent.resize(n + 1); // Khởi tạo mảng cha
  22.         rank.resize(n + 1, 0); // Khởi tạo độ cao ban đầu là 0
  23.         for (int i = 1; i <= n; i++) parent[i] = i; // Mỗi đỉnh là một tập riêng ban đầu
  24.     }
  25.  
  26.     // Tìm tập cha của đỉnh u
  27.     int find(int u) {
  28.         if (u != parent[u]) parent[u] = find(parent[u]); // Áp dụng đường đi nén để tối ưu
  29.         return parent[u];
  30.     }
  31.  
  32.     // Hợp nhất hai tập chứa u và v
  33.     bool unionSet(int u, int v) {
  34.         u = find(u); // Tìm tập cha của u
  35.         v = find(v); // Tìm tập cha của v
  36.         if (u == v) return false; // Nếu u và v cùng tập, không thể hợp nhất
  37.         if (rank[u] < rank[v]) swap(u, v); // Đảm bảo tập có độ cao thấp hơn được gộp vào tập cao hơn
  38.         parent[v] = u; // Hợp nhất tập v vào tập u
  39.         if (rank[u] == rank[v]) rank[u]++; // Tăng độ cao nếu hai tập có cùng độ cao
  40.         return true;
  41.     }
  42. };
  43.  
  44. // Tìm cây khung nhỏ nhất (MST) bằng thuật toán Kruskal
  45. // Có thể bỏ qua một cạnh cụ thể `ignoreEdge` nếu được chỉ định
  46. vector<Edge> findMST(int n, const vector<Edge>& edges, Edge ignoreEdge = {-1, -1, -1}) {
  47.     UnionFind uf(n); // Khởi tạo Union-Find
  48.     vector<Edge> mstEdges; // Lưu các cạnh của MST
  49.     int totalCost = 0; // Tổng chi phí của MST
  50.  
  51.     for (const Edge& edge : edges) {
  52.         if (edge.u == ignoreEdge.u && edge.v == ignoreEdge.v && edge.c == ignoreEdge.c) continue; // Bỏ qua cạnh ignoreEdge
  53.         if (uf.unionSet(edge.u, edge.v)) { // Nếu hợp nhất được u và v (không tạo chu trình)
  54.             mstEdges.push_back(edge); // Thêm cạnh vào MST
  55.             totalCost += edge.c; // Cộng chi phí của cạnh vào tổng chi phí
  56.         }
  57.     }
  58.  
  59.     if (mstEdges.size() == n - 1) return mstEdges; // Trả về MST nếu có đủ n-1 cạnh
  60.     return {}; // Trả về rỗng nếu không tìm được MST hợp lệ
  61. }
  62.  
  63. int main() {
  64.     int n, m, k; // n: số đỉnh, m: số cạnh, k: số kế hoạch cần tìm
  65.     cin >> n >> m >> k;
  66.  
  67.     vector<Edge> edges(m); // Danh sách các cạnh
  68.     for (int i = 0; i < m; i++) {
  69.         cin >> edges[i].u >> edges[i].v >> edges[i].c; // Nhập cạnh với u, v và chi phí c
  70.     }
  71.  
  72.     sort(edges.begin(), edges.end()); // Sắp xếp các cạnh theo chi phí tăng dần (chuẩn bị cho Kruskal)
  73.  
  74.     // Tìm cây khung nhỏ nhất ban đầu (MST đầu tiên)
  75.     vector<Edge> mst = findMST(n, edges);
  76.     if (mst.empty()) { // Nếu không tìm được MST hợp lệ
  77.         cout << -1 << endl; // In -1 và thoát
  78.         return 0;
  79.     }
  80.  
  81.     // Priority queue để lưu các tổng chi phí của các MST, sắp xếp theo thứ tự tăng dần
  82.     priority_queue<int, vector<int>, greater<int>> costs;
  83.     // Tính tổng chi phí của MST ban đầu và đưa vào priority queue
  84.     costs.push(accumulate(mst.begin(), mst.end(), 0, [](int sum, const Edge& e) { return sum + e.c; }));
  85.  
  86.     // Tìm các cây khung khác bằng cách loại bỏ lần lượt từng cạnh trong MST
  87.     for (const Edge& e : mst) {
  88.         vector<Edge> newMST = findMST(n, edges, e); // Tìm cây khung mới khi bỏ cạnh e
  89.         if (!newMST.empty()) { // Nếu tìm được cây khung mới hợp lệ
  90.             // Tính tổng chi phí của cây khung mới
  91.             int cost = accumulate(newMST.begin(), newMST.end(), 0, [](int sum, const Edge& e) { return sum + e.c; });
  92.             costs.push(cost); // Thêm tổng chi phí vào priority queue
  93.         }
  94.     }
  95.  
  96.     // Lấy cây khung thứ k (nếu có)
  97.     for (int i = 1; i < k; i++) {
  98.         if (costs.empty()) { // Nếu không còn cây khung nào trong priority queue
  99.             cout << -1 << endl; // In -1 và thoát
  100.             return 0;
  101.         }
  102.         costs.pop(); // Bỏ cây khung nhỏ nhất hiện tại để tiến đến cây tiếp theo
  103.     }
  104.  
  105.     // In tổng chi phí của cây khung thứ k (nếu có)
  106.     cout << (costs.empty() ? -1 : costs.top()) << endl;
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
5 6 2
1 2 2
1 3 4
2 4 3
2 5 1
3 5 5
stdout
copy 
11
https://ideone.com/xvXOYs
language:
C++14 (gcc 8.3)
created:
5 days 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!