Tóm tắt đề bài

Cho một hệ thống gồm \(N\) máy chủ. Giữa hai máy chủ \(u\) và \(v\) có thể có một cáp kết nối với dung lượng truyền tải \(C_{u,v}\). Tốc độ truyền dữ liệu tổng cộng \(F_{u,v}\) giữa hai máy chủ là tổng dung lượng của tất cả các đường đi không giao nhau về cạnh giữa chúng (theo định lý Luồng cực đại - Cắt tối thiểu, đây chính là giá trị luồng cực đại giữa \(u\) và \(v\)).

Cho trước ma trận \(F\) kích thước \(N \times N\), nhiệm vụ của bạn là tìm một ma trận dung lượng cáp \(C\) (với \(C_{u,v} = C_{v,u}\) và \(C_{u,u} = 0\)) sao cho tốc độ truyền tải giữa mọi cặp \((u, v)\) đúng bằng \(F_{u,v}\). Nếu không tồn tại cách kết nối nào, in ra NO.

Phân tích

1. Định lý Gomory-Hu Tree: Trong một đồ thị vô hướng với các trọng số cạnh không âm, giá trị luồng cực đại giữa mọi cặp đỉnh có thể được biểu diễn thông qua một cấu trúc cây gọi là cây Gomory-Hu. Trên cây này, luồng cực đại giữa hai đỉnh \(u\) và \(v\) bằng trọng số của cạnh nhỏ nhất trên đường đi duy nhất giữa \(u\) và \(v\) trên cây.
2. Tính chất của \(F_{u,v}\): Theo bài toán, \(F_{u,v}\) là giá trị luồng cực đại. Một tính chất quan trọng của luồng cực đại trong đồ thị vô hướng là:
   
   \[ F_{u,v} \geq \min(F_{u,w}, F_{w,v}) \quad \forall u, v, w \]
   
   Đây được gọi là bất đẳng thức tam giác cho luồng cực đại. Nếu ma trận \(F\) không thỏa mãn điều này cho mọi bộ ba đỉnh, sẽ không tồn tại đồ thị nào thỏa mãn.
3. Cây khung cực đại (Maximum Spanning Tree - MST): Một cách tiếp cận phổ biến để dựng đồ thị từ ma trận luồng là sử dụng thuật toán Kruskal để tìm cây khung cực đại dựa trên các giá trị \(F_{u,v}\). Nếu một giải pháp tồn tại, cây khung cực đại này chính là một cấu trúc ứng viên tiềm năng (giống như cây Gomory-Hu nhưng với các cạnh có trọng số bằng chính giá trị \(F_{u,v}\)).

Hướng giải quyết

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

1. Kiểm tra tính hợp lệ cơ bản:
   • \(F_{i,i} = 0\).
   • \(F_{i,j} = F_{j,i}\).
   • \(F_{i,j} \geq 0\).
2. Xây dựng Cây khung cực đại (MST):
   • Coi \(N\) máy chủ là các đỉnh của một đồ thị đầy đủ, trong đó cạnh giữa \(u\) và \(v\) có trọng số là \(F_{u,v}\).
   • Sử dụng thuật toán Kruskal (với DSU) để tìm cây khung cực đại. Chúng ta ưu tiên các cạnh có trọng số lớn nhất.
   • Nếu sau khi chạy Kruskal mà đồ thị không liên thông (số cạnh chọn được \(< N-1\)) và \(N > 1\), thì không thể thỏa mãn (trừ khi các giá trị \(F\) còn lại đều bằng 0).
3. Kiểm tra lại ma trận \(F\) trên cây:
   • Sau khi có cây khung cực đại, với mỗi cặp đỉnh \((u, v)\), ta tính giá trị luồng cực đại trên cây này (tức là giá trị cạnh nhỏ nhất trên đường đi từ \(u\) đến \(v\)). Gọi giá trị này là \(M_{u,v}\).
   • So sánh \(M_{u,v}\) với \(F_{u,v}\) ban đầu. Nếu tồn tại bất kỳ cặp nào mà \(M_{u,v} \neq F_{u,v}\), kết luận NO.
4. Xuất kết quả:
   • Nếu vượt qua các bước kiểm tra, in ra YES.
   • Ma trận \(C\) chính là các cạnh thuộc cây khung cực đại đã tìm được. Các cặp không có cạnh trong cây thì \(C_{u,v} = 0\).

Tại sao cách này đúng?

Nếu tồn tại một đồ thị thỏa mãn ma trận \(F\), thì các giá trị trong \(F\) phải tuân thủ cấu trúc của một cây Gomory-Hu. Việc dựng MST trên ma trận \(F\) giúp ta tìm ra cấu trúc cây đó. Nếu cấu trúc cây này không tái tạo lại được đúng ma trận \(F\), nghĩa là ma trận \(F\) vi phạm tính chất của luồng cực đại trong đồ thị vô hướng.

Độ phức tạp

• Thời gian: \(O(T \times (N^2 \log N + N^2))\) trong đó \(N^2 \log N\) là thời gian sắp xếp các cạnh để tìm MST và \(N^2\) là thời gian kiểm tra lại ma trận bằng cách duyệt cây (BFS/DFS từ mỗi đỉnh). Với \(N \leq 200\), độ phức tạp này hoàn toàn khả thi.
• Bộ nhớ: \(O(N^2)\) để lưu trữ ma trận.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Cấu trúc Disjoint Set Union để tìm MST
struct DSU {
    vector<int> p;
    DSU(int n) : p(n, -1) {}
    int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (p[a] > p[b]) swap(a, b);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

struct Edge {
    int u, v;
    ll w;
};

void solve(int tc) {
    int N;
    if (!(cin >> N)) return;
    vector<vector<ll>> F(N, vector<ll>(N));
    bool ok = true;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> F[i][j];
        }
    }

    // Kiểm tra tính đối xứng và đường chéo chính
    for (int i = 0; i < N; ++i) {
        if (F[i][i] != 0) ok = false;
        for (int j = 0; j < N; ++j) {
            if (F[i][j] != F[j][i] || F[i][j] < 0) ok = false;
        }
    }

    if (!ok) {
        cout << "Case #" << tc << ": NO\n";
        return;
    }

    if (N == 1) {
        cout << "Case #" << tc << ": YES\n0\n";
        return;
    }

    // Tìm cây khung cực đại (MST)
    vector<Edge> all_edges;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            all_edges.push_back({i, j, F[i][j]});
        }
    }
    sort(all_edges.begin(), all_edges.end(), [](const Edge& a, const Edge& b) {
        return a.w > b.w;
    });

    DSU dsu(N);
    vector<Edge> mst_edges;
    for (auto &e : all_edges) {
        if (dsu.unite(e.u, e.v)) {
            mst_edges.push_back(e);
        }
    }

    if (mst_edges.size() != N - 1) {
        cout << "Case #" << tc << ": NO\n";
        return;
    }

    // Xây dựng danh sách kề cho cây MST
    vector<vector<pair<int, ll>>> adj(N);
    for (auto &e : mst_edges) {
        adj[e.u].push_back({e.v, e.w});
        adj[e.v].push_back({e.u, e.w});
    }

    // Kiểm tra xem luồng cực đại trên cây có khớp với ma trận F không
    for (int s = 0; s < N; ++s) {
        vector<ll> min_edge(N, -1);
        queue<int> q;
        q.push(s);
        min_edge[s] = 2e18; // Vô cùng
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &[v, w] : adj[u]) {
                if (min_edge[v] == -1) {
                    min_edge[v] = min(min_edge[u], w);
                    q.push(v);
                }
            }
        }
        for (int t = 0; t < N; ++t) {
            if (s == t) continue;
            if (min_edge[t] != F[s][t]) {
                cout << "Case #" << tc << ": NO\n";
                return;
            }
        }
    }

    // Nếu mọi thứ khớp, in kết quả
    cout << "Case #" << tc << ": YES\n";
    vector<vector<ll>> C(N, vector<ll>(N, 0));
    for (auto &e : mst_edges) {
        C[e.u][e.v] = C[e.v][e.u] = e.w;
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cout << C[i][j] << (j == N - 1 ? "" : " ");
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        solve(tc);
    }
    return 0;
}