let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

QBBUILD - Xây dựng đường

solution.md

Đề bài yêu cầu tìm một đồ thị con sao cho đồ thị đó chứa đủ các đỉnh đặc biệt, và tổng trọng số các cạnh trên đồ thị là nhỏ nhất.

Gọi \(G = (V, E)\) là đồ thị đề cho, \(S \subset V\) là tập các đỉnh đặt biệt. Gọi \(G' = (V', E')\) là đồ thị kết quả. Ta thấy ngay 2 điều sau:

  • \(G'\) là cây.
  • Các đỉnh treo của \(G'\) phải là đỉnh đặc biệt. Nói cách khác: \(\forall u \in V', \mathrm{deg}(u) = 1 \implies u \in S\).

Sở dĩ có 2 điều trên là do mọi cạnh không cần thiết trong \(G\) sẽ bị loại bỏ.

Ngoài ra, ta có thêm nhận xét sau về đồ thị dạng cây: Nếu cây có một đỉnh bậc \(k\), thì cây đó có ít nhất \(k\) đỉnh treo.

Từ đó, suy ra \(G'\) sẽ có một trong những dạng sau:

(Lưu ý, trong các hình bên dưới, đỉnh trắng là đỉnh đặc biệt, đỉnh đen là đỉnh ở các giao lộ trên cây, các đỉnh nằm trên một đường thẳng sẽ không được vẽ)

(1) 2 đỉnh bậc 1, tất cả các đỉnh còn lại bậc 2

alt

(2) 3 đỉnh bậc 1, 1 đỉnh bậc 3, các đỉnh còn lại bậc 2

alt

(3) 4 đỉnh bậc 1, 1 đỉnh bậc 4, các đỉnh còn lại bậc 2

alt

(4) 4 đỉnh bậc 1, 2 đỉnh bậc 3, các đỉnh còn lại bậc 2

alt

Trong các hình trên, mỗi cạnh được hiểu là một dãy các đỉnh bậc 2, tạo thành dạng đường thẳng.

Ta có nhận xét quan trọng sau: Các cạnh trong những hình minh họa trên là đường đi ngắn nhất trên \(G\). Từ nhận xét này, ta có thuật toán duyệt như sau:

  • Dùng Floyd để tính đường đi ngắn nhất giữa mọi cặp đỉnh.
  • Với mỗi dạng trong 4 dạng đồ thị, thực hiện duyệt để gán nhãn các đỉnh và tính tổng các đường đi ngắn nhất để được trọng số của đồ thị.
  • Kết quả của bài toán sẽ là cách gán cho tổng nhỏ nhất.

Tuy nhiên, cài đặt cách giải này quá dài do có đến 4 trường hợp cần xét. Nếu để ý kĩ, có thể thấy trường hợp (4) là dạng tổng quát của tất cả các trường hợp còn lại. Ví dụ, nếu gộp 2 đỉnh đen của (4) lại, thì ta có được trường hợp (3).

Vậy, chỉ cần duyệt trường hợp (4), tức là chọn 2 đỉnh đen (u, v) sau đó duyệt các hoán vị của 4 đỉnh đặc biệt và tính tổng các cạnh trên hình minh họa. Lưu ý không cần xét \(u \ne v\); u, v không phải đỉnh đặc biệt hoặc bất cứ điều kiện gì khác.

Độ phức tạp thuật toán: \(O(n^3 + 4! n^2)\)

main.cpp
Open in Github Download
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
 
int a[101][101];
 
#define forn(i) for (int i = 1; i <= n; i++)
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;

    int s[4];
    for (int &u : s) cin >> u;

    forn(i) forn(j) a[i][j] = 1e8;
    forn(i) a[i][i] = 0;
    for (int u, v, w; cin >> u >> v >> w;) {
        a[u][v] = a[v][u] = w;
    }

    // Floyd
    forn(k) forn(i) forn(j) {
        if (a[i][j] > a[i][k] + a[k][j]) a[i][j] = a[i][k] + a[k][j];
    }

    // Create all permutation of `s` and put them in `permute`
    sort(s, s + 4);
    int permute[96];
    for (int i = 0; i < 24; i++) {
        next_permutation(s, s + 4);
        memcpy(permute + 4 * i, s, 16);
    }

    int res = 1e8;
    forn(u) forn(v) {
        for (int i = 0; i < 24; i++) {
            int x = a[u][v];
            x += a[u][permute[0 + 4 * i]];
            x += a[u][permute[1 + 4 * i]];
            x += a[v][permute[2 + 4 * i]];
            x += a[v][permute[3 + 4 * i]];
            res = min(res, x);
        }
    }
    cout << res << endl;
}
Comments