Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #3

Coding Challenge #3 là một bài toán về đường đi ngắn nhất, với tập cạnh có trọng số. Bài toán này là phiên bản tổng quát hoá trên đồ thị của bài toán đổ xăng nổi tiếng mà ắt hẳn mọi người đều đã trải qua một lần. Điểm thú vị của dạng bài này chính là việc chúng ta sẽ cần tư duy để tạo ra một đồ thị mới nhằm có thể nắm đủ thông tin bài toán. Trong 3 Coding Challenge, đây chính là bài toán thử thách nhất.

Bài toán này ghi nhận 21 bài giải thành công với lời giải nhanh nhất chỉ tốn 43 phút kể từ lúc đề bài Coding Challenge #3 được công bố. Đội ngũ Tạp chí VNOI đã chọn ra 2 lời giải cho bài toán này đến từ các độc giả của Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ

Coding Challenge #3 - Đổ Xăng

Đổ Xăng

Vương quốc VNOI gồm ~n~ thành phố được liên kết với nhau bằng ~m~ con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ ~i~ kết nối hai thành phố ~u_i, v_i~, và sẽ tốn ~w_i~ lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới VNOI. Bạn xuất phát từ thành phố ~st~ và có dự định đi tới thành phố ~en~ bằng xe của mình. Tất nhiên để đi xe thì phải tốn nhiên liệu, và xe của bạn có một bình chứa được tối đa ~t~ lít xăng.

VNOI có ~s~ trạm xăng. Trạm xăng thứ ~i~ được phân bố ở thành phố ~p_i~ và có chi phí cho mỗi lít xăng là ~c_i~. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được ~t~ lít xăng thôi).

Bạn bắt đầu từ thành phố ~st~ và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ ~st~ tới ~en~.

Input

• Dòng đầu gồm 3 số nguyên ~n, m, s~ (~2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100~)
• Dòng tiếp theo gồm một số nguyên dương ~t~ (~1 \le t \le 10^5~) mô tả sức chứa của bình xăng.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i, v_i, w_i~ (~1 \le u_i, v_i \le n; 1 \le w_i \le t~) miêu tả con đường thứ ~i~.
• ~s~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~p_i, c_i~ (~1 \le p_i \le n; 1 \le c_i \le 100~) miêu tả trạm xăng thứ ~i~.
• Dòng cuối cùng gồm hai số nguyên dương ~st, en~ (~1 \le st, en \le n~) miêu tả vị trí bắt đầu và đích đến của bạn.

Output

• In ra số tiền ít nhất cần để đi chuyến đi.

Subtask

• Subtask ~1~ (~30~\%): ~n \le 100~; ~m \le 100~; ~t \le 500~
• Subtask ~2~ (~30~\%): ~t \le 500~
• Subtask ~3~ (~40~\%): Không giới hạn gì thêm.

Sample Input 1

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

Sample Output 1

5500

Sample Input 2

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

Sample Output 2

1340

Sample Input 3

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

Sample Output 3

61

Minh Họa Sample:

Sample 1:

Sample 2

Sample 3

Lời giải #1

Subtask 1: ~n, m \leq 100, t \leq 500~

Tags: DP, Dijkstra, Auxiliary Graph

Ta gọi ~f_{i, j}~ là số tiền ít nhất cần trả để đi đến đỉnh ~i~ và còn lại ~j~ lít xăng.

Với mỗi đỉnh ~f_{i, j}~ đã được tính, ta có thể chuyển trạng thái như sau:

• Mua thêm lít xăng nếu như đỉnh i tồn tại cây xăng ~f_{i, next_j}~ ~(j < next_j <= t)~. ~f_{i, next_j} = f_{i, j} + (next_j - j) * minCost_i~ với ~minCost_i~ là chi phí nhỏ nhất để mua ~1~ lít xăng tại đỉnh ~i~.
• Chuyển đến đỉnh ~v~ kề ~i~ nếu như ~j >= w~. ~f_{v, j - w} = f_{u, j}~

Độ phức tạp: ~O((n \times t + (m + n \times t \times t)) \times log_2(n \times t))~

Subtask 2: ~t \leq 500~

Tags: Dijkstra, Auxiliary Graph.

Vẫn từ ý tưởng cũ, để dễ xử lí, ta tạo đỉnh ảo cho mỗi ~f_{i, j}~. Ở subtask 1, ta thấy rằng việc chuyển trạng thái cho ~f_{i, next_j}~ là khá lớn. Vậy nên, thay vì phải duyệt hết những ~next_j~, ta chỉ cần chuyển đến trạng thái ~f_{i, j + 1}~. Lúc này, số lượng cạnh cần xét sẽ giảm đi đáng kể !

Độ phức tạp: ~O((n \times t + (m + n \times t)) \times log_2(n \times t))~

Subtask 3: Không có giới hạn gì thêm

Tags: Dijkstra, Auxiliary Graph.

Ta thấy rằng thay vì xem xét tất cả những đỉnh trong đồ thị gốc, ta chỉ quan tâm đến những đỉnh đặc biệt, những đỉnh này là những đỉnh mà có thể ảnh hưởng đến hàm ~f~ của chúng ta. Đầu tiên, ta định nghĩa những đỉnh đặc biệt là những đỉnh hoặc là ~st~, hoặc là ~en~, hoặc là tồn tại ít nhất ~1~ cây xăng ở nó, và khi ta đến đỉnh đặc biệt, ta buộc phải mua lít xăng (nếu có cây xăng). Ta dễ dàng thấy được số lượng đỉnh đặc biệt là rất là ít, chỉ khoảng ~\leq 101~!. Vậy nên, Ta sẽ xem xét xem với cặp đỉnh ~(u, v)~ đặc biệt, chi phí thấp nhất để từ ~u \to v~ là bao nhiêu. Điều này ta có thể dễ dàng làm được bằng việc dijkstra trên đồ thị gốc. Ta gọi ~minCost_{u, v}~ là số lít nhỏ nhất để có thể đi từ ~u \to v~. Lúc này, hàm quy hoạch động của chúng ta giảm số lượng thái từ ~n \times t~ về ~s \times t~. Nhưng... vẫn còn quá lớn ?. Ta có một nhận xét quan trọng như sau: nếu khi đến đỉnh đặc biệt ~u~, vì ta buộc phải mua lít xăng ở ~u~, ta có thể giảm số trạng thái chiều ~j~ không phải là ~t~ mà là ~2 \times s~ (khoảng ~2 \times 10^4~, bé hơn ~t~ nhiều). Đầu tiên, ta quan sát rằng, khi tại đỉnh ~u~, ta chỉ nên mua đủ để đi đến ~v~ hoặc mua đầy tại ~u~ sau đó đi đến ~v~. Vậy nên, ta chỉ cần những trạng thái ~j~ hoặc là nằm trong tập ~\{minCost_{u, v}\}~, hoặc là nằm trong tập ~\{t - minCost_{u, v} \}~. Mà ta thấy số lượng phần tử trong của tập ~\{minCost_{u, v}\} \leq 10^4~ (Ta sẽ gọi đây là tập ~j~ đặc biệt).

Chứng minh:

• Xét hai đỉnh đặc biệt (u, v). Ta chia thành ~2~ trường hợp như sau:
  • Trường hợp ~1~: ~minCost_u < minCost_v~. Lúc này, để tối ưu, ta nên mua đầy lít xăng (là mua để làm đầy sức chứa) ở tại đỉnh ~u~, sao đó di chuyển đến đỉnh ~v~. Thì chi phí của chúng ta mới tối ưu được (thay vì từ đỉnh ~u~ đi đến đỉnh ~v~ xong rồi mua xăng). (Là cách chuyển trạng thái ~j~ từ ~t \to t - w~)
  • Trường hợp ~2~: ~minCost_u > minCost_v~. Lúc này, nếu như trường hợp ta còn đủ lít xăng, ta không nên mua tại ~u~ mà ta đi thẳng đến ~v~ (thì chắc chắn ~f_{v, x}~ không được tính từ ~f_{u, y}~. Trong chiều hướng ngược lại, ta nên mua đủ số lít xăng tại đỉnh ~u~ xong rồi đi đến đỉnh ~v~. (Là cách chuyển trạng thái ~j~ từ ~w \to 0~)

Xét Sample Input 2 trong đề bài, từ các thông tin sau, ta có thể xây dựng đồ thị như trên:

• ~SpecialNodes = \{ 1,2,3,5 \}~.
• ~SpecialCosts = \{ 0,20,40,60,80,100 \}~.
• Số lít xăng cần ít nhất từ ~1 \to 2~, ~1 \to 3~, ~2 \to 5~ lần lượt là ~80, 40, 80~. Chi phí mua xăng ít nhất tại đỉnh ~1, 2, 3~ lần lượt là ~8, 9, 2~. Ở đồ thị ảo ta xây dựng ở Sample Input 2, đường màu xanh là đường đi tối ưu, chính vì thế kết quả của chúng ta là ~1340~ !

Cuối cùng, ta sẽ có thuật toán như sau: Ta gọi:

• ~specialNodes~, ~specialCosts~ lần lượt là ~i~ và tập ~j~ đặc biệt.
• ~f_{i, j}~ là chi phí thấp nhất để đến đỉnh ~specialNode_i~ và còn dư ~specialCost_j~ lít.
• ~minCost_i~: chi phí nhỏ nhất để mua ~1~ lít xăng tại đỉnh ~specialNode_i~.
• ~minCost_{u, v}~: chi phí để đi từ ~u~ đến ~v~ mà mất ít lít xăng nhất.

Dễ dàng tính được ~minCost{u, v}~ bằng thuật toán dijkstra trên đồ thị ban đầu. Bước tiếp theo, ta sẽ thêm các cạnh vào đồ thị ảo. - Ta sẽ thêm tập cạnh ~f(u, minCost_{u, v}) \to f(v, 0)~ với trọng số là ~0~ nếu ~minCost_{u, v} \leq t~ (với ~u, v~ là những đỉnh đặc biệt) vào đồ thị ảo thể hiện mình sẽ đi đến ~v~ với đủ lít xăng. - Ta tiếp tục thêm tập cạnh ~f(u, t) \to f(v, t - minCost_{u, v})~ với trọng số là ~0~ nếu ~minCost_{u, v} \leq t~ (với ~u, v~ là những đỉnh đặc biệt) vào đồ thị ảo thể hiện mình đi đến ~v~ với đầy lít xăng. - Cuối cùng, ta thêm tập cạnh ~(u, t) \to (u, t')~ với trọng số là ~(t' - t) * minCost_u~ thể hiện ta mua lít xăng tại đỉnh ~u~.

Cuối cùng, ta sử dụng thuật toán dijkstra trong đồ thị ảo để tìm kết quả.

Lời giải #2

Subtask 1

Giới hạn: ~n \le 100~; ~m \le 100~; ~t \le 500~

Ý Tưởng:

• Ta đặt ~\text{costs}[i]~ là chi phí nhỏ nhất để mua ~1~ lít xăng ở thành phố ~i~. Nếu thành phố thứ ~i~ không có trạm xăng nào thì ta có thể coi ~\text{cost}[i] = +\infty~.
• Ta có thể mô hình bài toán bằng cách dựng một đồ thị ~G = (V, E)~ với mỗi đỉnh trong ~G~ đại diện cho một trạng thái của xe, gồm:
  • Thành phố xe đang dừng; và
  • Lượng xăng xe đang có. Nói cách khác, mỗi đỉnh có thể được biển diễn bằng một cặp số ~(i, f)~ với ~i~ là số hiệu thành phố và ~f~ là lượng xăng hiện tại của xe (~1 \leq i \leq n~, ~0 \leq f \leq t~).
• Ta sẽ có hai loại cạnh dựa trên hai loại hành động:
  • Mua ~1~ lít xăng: đồ thị chứa cạnh từ ~(i, f)~ đến ~(i, f + 1)~ (với điều kiện~f < t~) có trọng số ~\text{costs}[i]~.
  • Di chuyển sang thành phố khác trên con đường thứ ~i~: đồ thị chứa cạnh từ ~(u_i, r)~ đến ~(v_i, r - w_i)~ (với điều kiện ~r \geq w_i~) có trọng số ~0~.
• Kết quả bài toán ta cần tìm lúc này sẽ tương đương với việc tìm độ dài của đường đi ngắn nhất từ đỉnh ~(st, 0)~ đến một đỉnh ~(en, f)~ bất kì với ~0 \leq f \leq t~. Vì mọi trọng số đều không âm, ta dùng Dijkstra để tìm được độ dài ấy.

Độ Phức Tạp

• Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O((|V| + |E|)\log |V|)~ nếu ta cài đặt thuật toán Dijkstra với heap.
  • Vì với mỗi thành phố, ta có ~t + 1~ trạng thái khác nhau đại diện cho các mức xăng khác nhau, ta có ~V = O(n \cdot t)~ .
  • Vì với mỗi đường đi, ta sẽ có ~O(t)~ cạnh loại thứ hai được nêu trên và với mỗi thành phố, ta sẽ có ~O(t)~ cạnh loại thứ nhất được nếu trên, ta có ~E = O((n + m) \cdot t)~.

Code Minh Họa:

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

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;


vector<pair<int, int> > graph[MAX_N];
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
    }

    cin >> st >> en;
}

namespace Dijkstra {

    signed minimumCosts[MAX_N][MAX_T];
    priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > heap;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c))
            heap.emplace(c, make_pair(v, r));
    }

    void run() {
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(st, 0, 0);

        for (int x = 1; x <= n; ++x)
            sort(graph[x].begin(), graph[x].end());

        for (; !heap.empty();) {
            const auto [m, state] = heap.top();
            const auto &[x, r] = state;
            heap.pop();

            if (minimumCosts[x][r] != m)
                continue;

            if (x == en) {
                cout << m << '\n';
                return;
            }

            for (const auto &[w, y] : graph[x]) {
                if (r < w)
                    break;
                considerVertex(y, r - w, minimumCosts[x][r]);
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + costs[x]);
        }
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    Dijkstra::run();

    return 0;
}

Subtask 2

Giới hạn: ~n \le 1000~; ~m \le 10^4~; ~t \le 500~

Ý Tưởng:

• Vì chương trình giải cần phải chạy trong ~1~ giây (tương đương với khoảng ~10^8~ lệnh), giới hạn của subtask 2 có thể khiến chương trình chạy quá thời gian khi sử dụng thuật toán Dijkstra như trong subtask 1. Một thuật toán thay thế để tìm đường đi ngắn nhất ta có thể sử dụng để tìm đường đi ngắn nhất là SPFA (Shortest Path Faster Algorithm).

Độ Phức Tạp:

• Trong trường hợp tệ nhất, chương trình cài đặt với thuật toán SPFA có thể đạt độ phức tạp thời gian ~O(|V| \cdot |E|)~. Tuy nhiên, thời gian chạy trung bình của SPFA là rất nhanh, có thể được xem như thuật toán chạy với độ phức tạp ~O(|E|)~ trong trường hợp này.

Code Minh Họa:

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

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;


vector<pair<int, int> > graph[MAX_N];
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
    }

    cin >> st >> en;
}

namespace SPFA {

    signed minimumCosts[MAX_N][MAX_T];
    bool inqueue[MAX_N][MAX_T];
    queue<pair<int, int> > q;
    int result = INF;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c) && c < result) {
            if (v == en)
                minimize(result, c);
            if (!inqueue[v][r]) {
                q.emplace(v, r);
                inqueue[v][r] = true;
            }
        }
    }

    void run() {
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(st, 0, 0);

        for (int x = 1; x <= n; ++x)
            sort(graph[x].begin(), graph[x].end());

        for (; !q.empty(); q.pop()) {
            const auto &[x, r] = q.front();
            inqueue[x][r] = false;

            for (const auto &[w, y] : graph[x]) {
                if (r < w)
                    break;
                considerVertex(y, r - w, minimumCosts[x][r]);
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + costs[x]);
        }

        cout << result << '\n';
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    SPFA::run();

    return 0;
}

Subtask 3

Giới hạn: ~n \le 1000~; ~m \le 10^4~; ~t \le 10^5~

Ý Tưởng:

• Cách dựng đồ thị như trong hai Subtask đầu đều sẽ dẫn đến số lượng đỉnh và cạnh lớn trong Subtask 3 (trong trường hợp tệ nhất, ~|V|~ và ~|E|~ có thể lần lượt đạt khoảng ~10^8~ và hơn ~10^9~).
• Tạm không xét đến chi tiết giá xăng, ta đặt ~G_0 = (V_0, E_0)~ là đồ thị vô hướng có trọng số với mỗi đỉnh đại diện cho một thành phố và mỗi cạnh đại diện cho một đường đi ban đầu (~|V_0| = n~, ~|E_0| = m~).
• Ta nhận thấy rằng không phải thành phố nào cũng có trạm xăng. Vì vậy để giảm số đỉnh cần xem xét, ta có thể mô hình bài toán theo một cách khác như sau: Ta đặt ~G_1 = (V_1, E_1)~ là một đầy đủ với:
  • mỗi đỉnh đại diện cho một thành phố có trạm xăng hoặc là đich đến. ~\Rightarrow |V_1| = O(s)~
  • mỗi cạnh có trọng số đại diện cho lượng xăng tối thiểu cần dùng để di chuyển giữa hai đỉnh nếu bình chứa là vô hạn (trọng số này tương đương với đường đi ngắn nhất trong ~G_0~). ~\Rightarrow |E_1| = O(s^2)~
• Nếu ta xét thêm chi tiết giá xăng, ta có thể dựng một đồ thị ~G' = (V', E')~ từ ~G_1~ như cách ta có thể dựng đồ thị ~G~ từ ~G_0~ (bằng cách thêm chi tiết lượng xăng vào trạng thái, ...).
  • Khi này, số lượng đỉnh tối đa sẽ được giảm xuống còn khoảng ~10^7~ (~|V'| = O(s \cdot t)~).
  • Tuy nhiên, số lượng cạnh vẫn quá lớn để xử lý (~|E'| = O(s^2 \cdot t)~ lớn hơn ~10^9~)
• Để giảm số lượng cạnh cần xét, ta có một số nhận xét như sau: Trong ~G_1~, xét một cung từ ~x~ tới ~y~ với trọng số ~w~,
  • Nếu ~\text{costs}[x] \geq \text{costs}[y]~ hoặc ~y~ là đích đến thì trong ~G'~, ngoại trừ cạnh từ ~(x, w)~ đến ~(y, 0)~, ta không cần phải xem xét bất kì cạnh nào khác giữa từ thành phố ~x~ đến ~y~.

Giải thích:

  Trong cả hai trường hợp, ta không có lý do để cần có nhiều hơn ~w~ lít xăng ở thành phố ~x~ bởi:
  - Với trường hợp đầu, ta có thể mua xăng với giá rẻ hơn ở thành phố ~y~ (nếu ta không mua xăng ở thành phố ~y~ thì điều này đồng nghĩa với việc, ta muốn đến thành phố khác trong ~V_1~ từ ~x~).
  - Với trường hợp sau, ta không đi thêm bất kì đâu khi đã đến đích.

• Nếu ~\text{costs}[x] < \text{costs}[y]~ thì trong ~G'~, ngoại trừ cạnh từ ~(x, t)~ đến ~(y, t - w)~, ta không cần phải xem xét bất kì cạnh nào khác từ thành phố ~x~ đến ~y~.

Giải thích:

  Ta không có lý do để cần có ít hơn ~t~ lít xăng ở thành phố ~x~ bởi:
  - Nếu ta không mua xăng ở thành phố ~y~ thì điều này đồng nghĩa với việc, ta muốn đến thành phố khác trong ~V_1~ từ ~x~ (vì ~G_1~ là một đồ thị đầy đủ được định nghĩa như trên).
  - Nếu ta mua xăng ở thành phố ~y~ nhưng lại rời thành phố ~x~ với lượng xăng không đầy bình, chi phí sẽ không được tối ưu bởi thay vì mua ~1~ lít xăng ở ~y~, ta có thể làm điều tương tự với chi phí rẻ hơn ở thành phố ~x~.

• Với những nhất xét này, số lượng cạnh cần xét sẽ giảm xuống ~|E_2| = O(s^2 + s \cdot t)~ bởi ta chỉ xét tối đa một cạnh giữa hai thành phố khác nhau trong ~G_1~.

Mở rộng:

Số lượng cạnh và đỉnh cần xét có thể tiếp tục được giảm xuống ~O(s^2)~ bằng cách chỉ xét những đỉnh ~(x, f)~ có tối thiểu một cạnh đến đỉnh đại diện cho một thành phố khác ~x~.

Độ Phức Tạp:

• Để dựng được đồ thị ~G_1~, ta có thể cài đặt bằng cách chạy thuật toán Dijkstra nhiều lần với các thành phố có trạm xăng làm đỉnh nguồn. Vì vậy, bước này sẽ có độ phức tạp thời gian ~O(s \cdot n \cdot \log (n + m))~.
• Nếu ta tiếp tục sử dụng thuật toán SPFA trên đồ thị ~G_2 = (V_1, E_2)~, bước tìm kết quả cuối cùng sẽ có độ phức tạp ~O(s^2 + s \cdot t)~. Vì thế độ phức tạp tổng cho các bước xử lý chính có thể được xem như ~O(s \cdot n \cdot \log(n + m) + s^2 + s \cdot t)~.

Code Minh Họa:

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

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;

vector<pair<int, int> > graph[MAX_N];
long long minimumCost = INF;
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
        minimize(minimumCost, c);
    }

    cin >> st >> en;
}

namespace DijkstraAlgorithm {

    int vertexCount, vertexID[MAX_N], minimumDistances[MAX_S][MAX_S];
    vector<int> vertices, prices;

    void findMinimumDistances(const int source) {
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
        vector<int> distances(n + 1, INF);
        heap.emplace(distances[source] = 0, source);
        for (; !heap.empty();) {
            const auto [d, x] = heap.top();
            heap.pop();
            for (const auto &[w, y] : graph[x])
                if (minimize(distances[y], distances[x] + w))
                    heap.emplace(distances[y], y);
        }
        for (const int &destination : vertices)
            minimumDistances[vertexID[source]][vertexID[destination]] = distances[destination];
    }

    void run() {
        for (int i = 1; i <= n; ++i)
            if (costs[i] < INF || i == en) {
                vertexID[i] = (vertexCount++);
                vertices.push_back(i);
            } else
                vertexID[i] = -1;
        prices.resize(vertexCount);
        for (int i = 0; i < vertexCount; ++i) {
            findMinimumDistances(vertices[i]);
            prices[i] = costs[vertices[i]];
        }
    }

}

namespace SPFA {

    using namespace DijkstraAlgorithm;

    unordered_map<int, unordered_map<int, vector<int> > > graph;
    int endVertex, minimumCosts[MAX_S][MAX_T];
    bool inqueue[MAX_S][MAX_T];
    queue<pair<int, int> > q;
    int result = INF;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c) && c < result) {
            if (v == endVertex)
                result = c;
            else if (!inqueue[v][r]) {
                inqueue[v][r] = true;
                q.emplace(v, r);
            }
        }
    }

    void buildGraph() {
        endVertex = vertexID[en];
        for (int x = 0, y = 0; x < vertexCount; ++x)
            for (y = 0; y < vertexCount; ++y) {
                if (x == y || minimumDistances[x][y] > t)
                    continue;
                if (prices[x] >= prices[y] || y == endVertex) {
                    graph[x][minimumDistances[x][y]].push_back(y);
                    continue;
                }
                graph[x][t].push_back(y);
            }
    }

    void run() {
        buildGraph();
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(vertexID[st], 0, 0);

        for (; !q.empty(); q.pop()) {
            const auto &[x, r] = q.front();
            inqueue[x][r] = false;

            const auto outerElement = graph.find(x);

            if (outerElement != graph.end()) {
                const auto &innerElements = (outerElement -> second);
                const auto innerElement = innerElements.find(r);

                if (innerElement != innerElements.end()) {
                    for (const auto &y : (innerElement -> second))
                        considerVertex(y, r - minimumDistances[x][y], minimumCosts[x][r]);
                }
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + prices[x]);
        }

        cout << result << '\n';
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    DijkstraAlgorithm::run();
    SPFA::run();

    return 0;
}

Xin trân trọng cảm ơn các tác giả đã đồng hành cùng chuyên mục. Các tác giả có bài giải được đăng trong Tạp chí VNOI - Số 1 đã được đội ngũ Tạp chí VNOI liên hệ để nhận phần quà tri ân từ VNOI.

Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #2

Coding Challenge #2 tiếp tục là một bài toán đồ thị, với chủ đề về Cây Khung Nhỏ Nhất. Điểm đặc biệt của bài toán chính là ở việc chúng ta sẽ không chỉ đi tìm một cây khung, mà cần liên tiếp thực hiện thao tác tìm kiếm để cho ra K cây khung lớn nhất (một biến thể ngược của bài toán MST nổi tiếng).

Bài toán này ghi nhận 116 độc giả tham gia giải và 28 bài giải được trọn vẹn 100/100 điểm từ bộ test. Đội ngũ Tạp chí VNOI đã chọn ra 2 lời giải cho bài toán này đến từ các độc giả của Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ

Coding Challenge #2 - Đấu Thầu

Nước VNOI gồm ~n~ thành phố và đang có kế hoạch liên kết chúng bằng ~m~ con đường cao tốc hai chiều. Các con đường được đánh số từ 1 tới ~m~, con đường thứ ~i~ liên kết thành phố ~u_i~ với ~v_i~, và có lợi nhuận là ~w_i~ (các giá trị ~w_i~ phân biệt). Các con đường được thiết kế để tất cả các cặp thành phố đều có thể trực tiếp hoặc gián tiếp đi tới nhau.

Để xây dựng các con đường đó, chính quyền VNOI quyết định giao việc này cho ~k~ nhà thầu. Sau những vòng bỏ phiếu căng thẳng, các nhà thầu này được xếp ở các vị trí từ ~1~ tới ~k~ thể hiện sự ưu tiên trong việc chọn tuyến đường thi công.

Mỗi nhà thầu sẽ được chọn một tập hợp các con đường trong ~m~ đường cao tốc có sẵn trong kế hoạch, sao cho chúng không tạo ra bất kì chu trình nào và con đường không bị nhà thầu nào trước đó chọn. Giả sử, nếu nhà thầu chọn con đường ~\{1 \to 2; 2 \to 3; 3 \to 1; 4 \to 5\}~ là không thoả mãn, bởi vì có chu trình ~1 \to 2 \to 3 \to 1~. Lưu ý rằng ở ví dụ trên mũi tên được đánh hướng cho mục đích biểu diễn, còn trên thực tế thì các con đường là hai chiều.

Đầu tiên, nhà thầu thứ ~1~ sẽ được chọn trước, sau đó tới nhà thầu thứ ~2~, ... tới nhà thầu thứ ~k~. Tất nhiên với cách này, một số con đường sẽ không được xây dựng, nhưng ở giai đoạn đầu của dự án thì đây là chuyện bình thường.

Tất nhiên, mỗi nhà thầu đều muốn tối đa hoá lợi ích của mình, vậy nên khi được chọn các con đường, họ sẽ chọn tập con đường mang tới tổng lợi nhuận lớn nhất có thể.

Nhiệm vụ của bạn là tính toán trước cho chính quyền VNOI xem mỗi nhà thầu từ ~1~ tới ~k~ sẽ có lợi nhuận là bao nhiêu khi tất cả đều chọn tập con đường một cách tối ưu.

Input

• Dòng đầu tiên gồm 3 số nguyên ~n, m, k~ miêu tả số thành phố, số con đường cần xây dựng và số nhà thầu;
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên ~u_i, v_i, w_i~ miêu tả con đường thứ ~i~ trong kế hoạch, kết nối thành phố ~u_i~ với ~v_i~

Output

• Gồm ~k~ dòng, dòng thứ ~i~ chứa giá trị là tổng lợi nhuận của nhà thầu thứ ~i~ trong cách chia tối ưu.

Subtask

• Trong tất cả các test ~w_i \le 10^9~
• Có ~20~% test tương ứng ~20~% số điểm có ~n \le 10^5, m \le 5 \times 10^5; k = 1~.
• Có ~25~% test tương ứng ~25~% số điểm có ~n \le 10^3, m \le 10^4; k \le 1000~.
• Có ~35~% test tương ứng ~35~% số điểm có ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~.
• ~20~% số test còn lại tương ứng với ~20~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~.

Sample

Sample 1

Input

4 5 1
1 2 5   
2 3 4   
3 4 3   
4 1 2   
1 3 1

Output

12

Sample 2

Input

5 8 3
1 2 9
2 3 8
3 4 7
2 5 4
1 3 3
2 4 2
4 5 6
1 5 5

Output

30
14
0

Tóm Tắt Đề Bài

• Cho một đồ thị vô hướng liên thông ~G = (V, E)~ có ~n~ đỉnh và ~m~ cạnh mang trọng số dương.
• Thực hiện thao tác sau ~k~ lần:
  • Tìm tập cạnh ~E' \subseteq E~ sao cho:
    • ~E'~ không chứa chu trình;
    • ~E'~ có tổng trọng số lớn nhất có thể.
  • Xóa các cạnh trong ~E'~ khỏi ~E~ (~E \leftarrow E \setminus E'~).
  • Cho biết tổng trọng số của ~E'~ sau mỗi lần thực hiện thao tác.

Minh Họa Sample

Sample 1:

• Minh hoạ đồ thị sau mỗi lần thực hiện thao tác

• Minh họa tập cạnh được chọn bởi các thao tác

Sample 2:

• Minh họa đồ thị sau mỗi lần thực hiện thao tác

• Minh họa tập cạnh được chọn bởi các thao tác

Lời giải #1

Một số lưu ý

Đồ thị được cho trên đề bài không nhắc đến việc không tồn tại cạnh lặp.

Subtask 1: ~n\le 10^5,m\le 5\times 10^5,k=1~

Theo đề bài, các cạnh mà mỗi nhà thầu chọn không được tạo thành một chu trình. Điều này tương ứng với việc các cạnh đó phải là các cạnh của một rừng (forest).

Trong subtask 1, chỉ có duy nhất một nhà thầu nên ta có thể tóm tắt yêu cầu của subtask này như sau: Chọn ra một tập cạnh có tổng trọng số lớn nhất sao cho tập cạnh đó phải tạo thành một rừng.

Đây là dạng bài toán tìm cây khung lớn nhất trên đồ thị. Về cơ bản thì cách làm không khác gì cách làm bài toán tìm cây khung nhỏ nhất.

Về thuật toán tìm cây khung nhỏ nhất, các bạn có thể tìm hiểu tại đây.

Độ phức tạp: ~O(m\times log(m)+m\times log(n))~ (Kruskal) hoặc ~O((m+n)\times log(n))~ (Prim).

Subtask 2: ~n\le 10^3,m\le 10^4,k\le 1000~

Trong trường hợp có nhiều nhà đấu thầu hơn, rõ ràng:

• Nhà đấu thầu thứ nhất sẽ chọn các cạnh để tạo thành cây khung lớn nhất (như subtask 1).
• Từ nhà đấu thầu thứ hai, họ cũng sẽ chọn các cạnh để tạo thành cây khung lớn nhất từ các cạnh còn lại mà họ có thể chọn.

Như vậy, subtask này chỉ là tìm cây khung lớn nhất ~k~ lần tương ứng với ~k~ nhà đấu thầu. Với mỗi lần chọn được các cạnh cho một nhà đấu thầu, ta bỏ các cạnh đó đi để xét cạnh trên đồ thị mới cho các nhà đấu thầu sau.

Độ phức tạp: ~O(T\times k)~ với ~T~ là độ phức tạp cho mỗi lần tìm cây khung lớn nhất (subtask 1).

Subtask 3: ~n\le 10^3,m\le 5\times 10^5,k\le 10^4~

Vì giới hạn lớn nên ta không thể áp dụng cách tìm cây khung lớn nhất như cách làm của subtask 1/2.

Dựa trên thuật toán Kruskal, ta có một cách làm khác để giải subtask 2 như sau:

• Ta tạo ~k~ cây khung tương ứng với ~k~ nhà đấu thầu. Sắp xếp lại các cạnh theo trọng số giảm dần.
• Khi xét từng cạnh, nếu cạnh đó có thể thêm vào cây khung thứ nhất thì ta sẽ thêm. Trong trường hợp ngược lại, ta sẽ xét cây khung thứ hai, và cứ vậy đến cây khung thứ ~k~ (chọn cây khung có chỉ số nhỏ nhất mà ta có thể thêm cạnh).
• Cách duyệt này vẫn đảm bảo việc chọn ra được cây khung lớn nhất cho tất cả ~k~ nhà đấu thầu.

Tới đây ta có một nhận xét:

• Gọi ~f(i,j,p)~ là hàm kiểm tra tính liên thông của cặp đỉnh ~(i,j)~ trên cây khung thứ ~p~. ~f(i,j,p)=1~ khi hai đỉnh này cùng nằm trên một TPLT của cây khung thứ ~p~ và ~f(i,j,p)=0~ trong trường hợp ngược lại.
• Khi đó, ~f(i,j,p)\ge f(i,j,p+1)\forall 1\le i,j\le n,1\le p<k>
• Nói cách khác, tính liên thông của mọi cặp đỉnh ~(i,j)~ giảm dần theo chỉ số ~p~ của cây khung.
</k>

Với tính chất của hàm ~f(i,j,p)~, ta có thể thực hiện tìm kiếm nhị phân để tìm cây khung có chỉ số nhỏ nhất mà ~f(i,j,p)=0~ mỗi khi xét cạnh ~(i,j)~.

Độ phức tạp cho mỗi lần xét cạnh sẽ là ~O(log(n)\times log(k))~ hoặc có thể nhỏ hơn nếu thực hiện tối ưu như nén đường đi hay gộp theo kích cỡ.

Độ phức tạp: ~O(m\times log(n)\times log(k))~.

Subtask 4: ~n\le 10^5,m\le 5\times 10^5,k\le 10^4~

Việc dựng ~k~ cây khung một cách thủ công sẽ không thể thực hiện như subtask 3 vì ~n\times k\le 10^9~, giới hạn này là rất lớn để có thể lưu trữ.

Trên thực tế, ta không cần phải lưu hết trạng thái của các đỉnh vì nếu có đỉnh không phải là một trong hai đầu của bất kỳ cạnh nào của cây khung thì không cần phải lưu trữ. Vì thế nên ta có thể sử dụng std::map hoặc cây tiền tố (trie) để lưu tất cả những nút cần lưu trữ thông tin. Điều này giúp việc thực hiện các thao tác trên DSU cũng chỉ mất ~O(log(n))~.

Lưu ý: Cần phải cài đặt cẩn thận vì có thể sẽ bị TLE (time limit exceed).

Độ phức tạp: ~O(m\times log(n)\times log(k))~.

Lời giải #2

Subtask 1: Giới hạn: ~n \le 10^5, m \le 5 \times 10^5; k = 1~

Ý Tưởng:

• Vì số thao tác cần phải thực hiện ~k~ là ~1~, bài toán có thể được quy về tìm cây khung lớn nhất (ngược với bài toán tìm cây khung nhỏ nhất) trong đồ thị đã cho bởi:
  • Vì tập cạnh được chọn, tạm gọi là ~E'~, không được chứa chu trình, ~E'~ phải là một rừng.
  • Hơn nữa, vì đồ thị ban đầu liên thông, để tổng trọng số là lớn nhất, ~E'~ phải là một cây khung (rừng liên thông gồm ~n - 1~ cạnh). Nếu ~E'~ không liên thông, ta có thể thêm một cạnh mới mà không tạo ra chu trình, làm tăng tổng trọng số. Điều này mâu thuẫn với giả thiết tối ưu.
• Để tìm cây khung lớn nhất, ta có thể sử dụng thuật toán Kruskal với một thay đổi nhỏ: Thay vì sắp xếp các cạnh theo thứ tự tăng dần trọng số, ta sắp xếp giảm dần.

Cách chứng minh thứ nhất (ngắn gọn):

• Bài toán tìm cây khung lớn nhất trên đồ thị ~G = (V, E)~ có thể được quy về bài toán tìm cây khung nhỏ nhất trên đồ thị ~G' = (V, E)~ với cùng tập đỉnh và cạnh, nhưng với trọng số mới được đảo dấu (~w'_e = -w_e~ cho mọi cạnh ~e \in E~). Khi đó, cây khung nhỏ nhất của ~G'~ cũng chính là cây khung lớn nhất của ~G~.
• Thuật toán Kruskal có thể được dùng để tìm cây khung nhỏ nhất với các cạnh được duyệt theo thứ tự trọng số tăng dần. Khi áp dụng thuật toán trên đồ thị ~G'~, thứ tự này tương đương với việc duyệt các cạnh của ~G~ theo thứ tự trọng số giảm dần.

Cách chứng minh thứ hai (chi tiết):

Lưu ý: Cách chứng minh này phần lớn giống với cách minh tính đúng đắn của thuật toán Kruskal.

• Ta có thể chứng minh tính đúng đắn của ý tưởng trên bằng cách chứng minh quy nạp theo số lượng cạnh đã chọn với mệnh đề sau: "Với tập cạnh ~M~ được chọn bởi thuật toán tại mọi thời điểm, đồ thị luôn chứa một cây khung lớn nhất với tập cạnh ~T~ chứa mọi cạnh của ~M~".

  • Trường hợp cơ sở: Mệnh đề trên hiển nhiên đúng với trường hợp ban đầu, khi ~M~ không chứa bất kì cạnh nào bởi tập rỗng luôn là tập con của bất kì cây khung lớn nhất nào.
  • Bước quy nạp: Khi ta xem xét có nên thêm cạnh ~e~ vào ~M~ đang thỏa mệnh đề trên không, ta có ba trường hợp sau:
  1. ~M \cup \{e\}~ chứa chu trình (thêm cạnh ~e~ vào ~M~ tạo nên một chu trình): Thuật toán sẽ không thêm ~e~ vào ~M~. Vì vậy, mệnh đề sẽ vẫn thỏa bởi ~T~ cũng không thể chứa ~e~ (~T~ là một cây khung nên không chứa chu trình).
  2. ~T~ chứa ~e~: Mệnh đề trên tiếp tục thỏa.
  3. ~T~ không chứa ~e~: Khi thêm cạnh ~e~ vào ~T~, ta có ~T \cup {e}~ chứa một chu trình duy nhất có chứa cạnh ~e~. Chu trình này phải chứa ít nhất một cạnh ~f~ không ở trong ~M~. Nếu không, việc thêm ~e~ vào ~M~ đã tạo chu trình, tức rơi vào trường hợp đầu tiên.

  Vì cạnh ~f~ đã không được chọn bởi thuật toán trước đó, trọng số của cạnh ~f~ không thể lớn hơn trọng số cạnh ~e~ (~w_f \leq w_e~). Khi này, ta nhận thấy rằng cây khung với tập cạnh ~T' = T \cup \{e\} \setminus \{f\}~ cũng là cây khung lớn nhất bởi tổng trọng số của ~T'~ không nhỏ hơn tổng trọng số của ~T~. Mệnh đề vì thế vẫn tiếp tục được thỏa bởi ~M \cup \{e\}~ là tập con của tập cạnh ~T'~ của một cây khung lớn nhất.

Độ Phức Tạp:

• Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O(m \log m + n)~ bằng cách sử dụng cấu trúc dữ liệu Disjoint Set Union để quản lý các thành phần liên thông như trong bài toán tìm cây khung nhỏ nhất.

Giải thích:

• Bước khởi tạo cấu trúc dữ liệu Disjoint Set Union có thể có độ phức tạp ~O(n)~.
• Bước sắp xếp cạnh có độ phức tạp ~O(m \log m)~.
• Với mỗi lần xem xét một cạnh ~e = (u, v)~, ta cần kiểm tra hai đỉnh của cạnh ~e~ có cùng thuộc một thành phần liên thông không và nếu không thuộc thì ta có gộp hai thành phần liên thông chứa ~u~ và ~v~ lại. Nếu ta cài đặt cấu trúc dữ liệu Disjoint Set Union với cả hai phương pháp gộp theo kính cỡ và nén đường đi, một lần xem xét thêm cạnh như trên có độ phức tạp ~O(\alpha(n))~ với ~\alpha~ là hàm Ackermann nghịch đảo.

Vì ta duyệt ~m~ cạnh, bước xém xét hết tất cả các cạnh sẽ có độ phức tạp ~O(m \cdot \alpha(n))~.

Độ phức tạp tổng lúc này sẽ là ~O(m \log m) + O(m \cdot \alpha(n)) + O(n) = O(m \log m + n)~.

Lưu ý: Nếu ta chỉ dùng một trong phương pháp nêu trên khi cài đặt cấu trúc dữ liệu Disjoint Set Union, một lần xem xét thêm cạnh như trên có độ phức tạp ~O(\log(n))~. Khi này, độ phức tạp tổng sẽ là ~O(m \cdot (\log(m) + \log(n)) + n)~.

• Với cách cài đặt này, độ phức tạp bộ nhớ là ~O(n + m)~.

Giải thích:

• Lưu danh sách cạnh chiếm cần ~O(m)~ bộ nhớ.
• Cấu trúc dữ liệu Disjoint Set Union cần ~O(n)~ bộ nhớ.

Code Minh Họa:

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    DisjointSetUnion(const int n): roots(n, -1) {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    DisjointSetUnion dsu(n + 1);
    long long result = 0;

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges)
        if (dsu.unite(u, v))
            result += w;

    cout << result << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Subtask 2: Giới hạn: ~n \le 10^3, m \le 10^4; k \le 1000~

Ý Tưởng:

• Giới hạn của Subtask 2 cho phép chúng ta thực hiện ý tưởng đề cập trong Subtask 1 ~k~ lần mà vẫn đảm bảo được độ phức tạp thời gian cho phép. Cụ thể hơn, với mỗi thao tác, ta có thể thực hiện lại ý tưởng trong Subtask 1 rồi xóa tập cạnh được chọn bởi thao tác khỏi đồ thị để ta có thể xử lý các thao tác sau. >[!Note] Lưu ý: >Vì sau khi xóa cạnh khỏi đồ thị, đồ thị có thể không liên thông nữa, tập cạnh mà chúng ta cần tìm lúc này có thể là một rừng thay vì chỉ một cây khung: với mỗi thành phần liên thông trong đồ thị hiện tại, ta cần tìm cây khung lớn nhất trong thành phần liên thông đó; tập cạnh chúng ta cần tìm sẽ là tập cạnh được tạo bởi các cạnh của các khung đó.

Độ Phức Tạp:

• Ý tưởng trên có thể được cài đặt với độ phức tạp ~O(m \log m + k \cdot (n + m \cdot \alpha(n)))~.
• Độ phức tạp bộ nhớ sẽ tương tự như trong Subtask 1, tức ~O(n + m)~.

Code Minh Họa:

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion(const int n): roots(n, -1) {};

    void reload() {
        fill(roots.begin(), roots.end(), -1);
    }

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    DisjointSetUnion dsu(n + 1);
    vector<bool> removed(m);
    long long result = 0;

    sort(edges.rbegin(), edges.rend());

    for (int t = 0; t < k; ++t) {
        result = 0;
        dsu.reload();

        for (int i = 0; i < m; ++i) {
            if (removed[i])
                continue;
            const auto &[w, u, v] = edges[i];
            if (dsu.unite(u, v)) {
                removed[i] = true;
                result += w;
            }
        }

        cout << result << '\n';
    }
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Subtask 3: Giới hạn: ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~

Ý Tưởng:

• Đặt ~S_{i, j}~ (với ~1 \leq i \leq k~ và ~0 \leq j \leq m~) là tập cạnh được chọn trong thao tác thứ ~i~ sau khi đã xét ~j~ cạnh trong danh sách các cạnh được sắp xếp theo trọng số giảm dần. Chi tiết và ví dụ:

  Lưu ý: Phần này trình bày chi tiết cách xác định tập cạnh ~S_{i, j}~ theo định nghĩa trên. Nội dung này có thể không bắt buộc phải đọc để hiểu ý tưởng chính, mà chỉ nhằm làm rõ hơn định nghĩa ~S_{i, j}~.

  Chi Tiết

  • Với ~j = 0~, ta có ~S_{i,j} = \emptyset~ vì chưa có cạnh nào được xét ở thời điểm bắt đầu thao tác thứ ~i~.
  • Với ~1 \leq j \leq m~, đặt ~e~ là cạnh thứ ~j~. Khi đó, ta có thể xác định ~S_{i, j}~ như sau:
    • ~S_{i, j} = S_{i, j - 1}~ nếu một trong hai điều kiện sau thỏa:
      • Cạnh ~e~ đã được chọn trước đó: ~\exists z ((1 \leq z < i) \land (e \in S_{z,j}))~
      • Việc thêm cạnh ~e~ sẽ tạo thành một chu trình trong tập hiện tại: ~S_{i, j - 1} \cup \{e\}~ chứa ít nhất một chu trình.
    • ~S_{i, j} = S_{i, j - 1} \cup \{e\}~ trong trường hợp còn lại.

  Ví dụ

  • Với test ví dụ thứ hai, các cạnh sau khi được sắp xếp giảm dần theo trọng số có thứ tự như sau:

    ~ \begin{array}{|c|*{8}{c|}} \hline \textbf{i} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline e_i & (1,2) & (2,3) & (3,4) & (4,5) & (1,5) & (2,5) & (1,3) & (2,4) \\ \hline w_i & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 \\ \hline \end{array} ~

  • Giá trị ~S_{i, j}~ được tính như bảng sau:

    ~ \begin{array}{|c|*{3}{l|}} \hline \textbf{ j\i } & \textbf{1} & \textbf{2} & \textbf{3} \\ \hline 0 & \emptyset & \emptyset & \emptyset \\ \hline 1 & \{(1,2)\} & \emptyset & \emptyset \\ \hline 2 & \{(1,2), (2,3)\} & \emptyset & \emptyset \\ \hline 3 & \{(1,2), (2,3), (3,4)\} & \emptyset & \emptyset \\ \hline 4 & \{(1,2), (2,3), (3,4), (4,5)\} & \emptyset & \emptyset \\ \hline 5 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5)\} & \emptyset \\ \hline 6 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5)\} & \emptyset \\ \hline 7 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5), (1, 3)\} & \emptyset \\ \hline 8 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5), (1, 3), (2, 4)\} & \emptyset \\ \hline \end{array} ~

• Ta nhận thấy rằng nếu cạnh thứ ~j~, gọi là ~e_j~, được chọn trong bất kì một thao tác ~i~ nào thì ~i~ chính là giá trị nhỏ nhất sao cho với mọi thao tác ~z~ trước ~i~ (~1 \leq z < i~), việc thêm ~e_j~ vào ~S_{z, j - 1}~ sẽ tạo thành chu trình. Nếu không, cạnh ~e_j~ đã nên được chọn trước thao tác ~i~. Ta có: ~i = \min\{x \mid \forall z ((1 \leq z < x) \rightarrow C(S_{z, j - 1} \cup \{e_j\})) \}~ với ~C~ là mệnh đề "đồ thị con tạo bởi tập cạnh ~A~ chứa ít nhất một chu trình".

• Dựa vào nhận xét trên, ta có thể duyệt qua từng cạnh và dùng kỹ thuật chặt nhị phân để xác định thao tác sớm nhất có thể chứa cạnh đó mà không tạo chu trình. Để kiểm tra việc một chu trình có thể xuất hiện hay không khi thêm một cạnh nào đó, với mỗi thao tác, ta sử dụng một cấu trúc dữ liệu để quản lý thành phần liên thông trong suốt quá trình duyệt qua các cạnh. Ý tưởng cài đặt: Ta có thể sử dụng ~k~ cấu trúc dữ liệu Disjoint Set Union để quản lý thành phần liên thông giữa ~n~ đỉnh cho ~k~ thao tác.

Độ Phức Tạp:

• Ý tưởng trên có thể được cài đặt với độ phức tạp ~O(m \log m + k \cdot n + m \log k \cdot \alpha(n))~.

  Giải thích:

  • Bước sắp xếp cạnh có độ phức tạp ~O(m \log m)~ (tương tự như trong Subtask 1).
  • Việc khởi tạo ~k~ cấu trúc dữ liệu Disjoint Set Union để quản lý thành phần liên thông trên ~n~ đỉnh có độ phức tạp ~O(k \cdot n)~.
  • Bước xử lý các cạnh có độ phức tạp ~O(m \log k \cdot \alpha(n))~.
    • Với mỗi lần xét cạnh, chúng ta tìm được thao tác (nếu tồn tại) mà chứa được cạnh đang xét sau tối đa ~O(\log k)~ bước chặt nhị phân.
    • Với mỗi lần chặt nhị phân, việc kiểm tra việc hai đỉnh của cạnh đang xét có đang thuộc cùng một thành phần liên thông có độ phức tạp ~O(\alpha(n))~ (tương tự như trong Subtask 1).
    • Chúng ta phải xét qua ~O(m)~ cạnh.
    • Ngoài ra, chúng ta có thể phải cập nhật thành phần liên thông cuối mỗi lần xét cạnh với độ phức tạp ~O(\alpha(n))~.

Độ phức tạp tổng vì thế là ~O(m \cdot (\log k \cdot \alpha(n) + \alpha(n))) = O(m \log k \cdot \alpha(n))~

• Với cách cài đặt này, độ phức tạp bộ nhớ là ~O(m + k \cdot n)~. Giải thích:
  • Lưu danh sách cạnh chiếm cần ~O(m)~ bộ nhớ (tương tự như trong Subtask 1).
  • Lưu ~k~ cấu trúc dữ liệu Disjoint Set Union cần ~O(k \cdot n)~ bộ nhớ.

Code Minh Họa:

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    DisjointSetUnion(const int n): roots(n, -1) {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
long long result[MAX_K];
vector<DisjointSetUnion> graphs;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    int low = 0, middle = 0, high = 0;

    graphs.resize(k + 1, DisjointSetUnion(n + 1));

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges) {
        low = 0;
        high = k + 1;
        while (low + 1 < high) {
            middle = low + high >> 1;
            if (graphs[middle].checkConnected(u, v))
                low = middle;
            else
                high = middle;
        }
        if (high <= k) {
            graphs[high].unite(u, v);
            result[high] += w;
        }
    }

    for (int i = 1; i <= k; ++i)
        cout << result[i] << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Subtask 4: Giới hạn: ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~

Ý Tưởng:

Lưu ý: Ý tưởng chính sử dụng trong Subtask này cũng giống như trong Subtask 3. Điểm khác biệt chính nằm ở hướng cài đặt ý tưởng.

• Nhận xét về độ phức tạp của cách cài đặt cho Subtask 3: Với độ phức tạp của cách cài đặt cho Subtask 3, ta nhận thấy rằng việc quản lý các thành phần liên thông cho từng thao tác, là phần có chi phí tính toán nặng trong trường hợp tệ nhất (với độ phức tạp ~O(k \cdot n)~). Mặt khác, các bước xử lý còn lại có chi phí tính toán chấp nhận được. Vì vậy, nếu ta muốn cải thiện ý tưởng đó, ta cần phải tối ưu những bước xử lý liên quan tới quản lý thành phần liên thông.

• Ta có một số nhận xét như sau:

  • Với cách cài đặt đề cập trong Subtask 3, ta cần phải quan lý tổng cộng ~k \cdot n~ đỉnh (mỗi cấu trúc dữ liệu Disjoint Set Union quản lý ~n~ đỉnh). Tuy nhiên, trong suốt quá trình xử lý ~m~ cạnh, chỉ có tối đa ~2 \cdot m~ đỉnh thuộc các thành phần liên thông có kích thước lớn hơn ~1~. Giải thích: Mỗi cạnh được xét nếu được thêm vào chỉ có thể làm tăng số lượng đỉnh nằm trong một thành phần liên thông không đơn lẻ thêm tối đa ~2~ đỉnh.

  • Khi kiểm tra hai đỉnh ~u~ và ~v~ khác nhau có thuộc cùng một thành phần liên thông hay không, ta nhận thấy rằng: nếu một trong hai đỉnh thuộc một thành phần có kích thước bằng ~1~ thì ~u~ và ~v~ chắc chắn không cùng thành phần liên thông. ~\Rightarrow~ Dựa trên những nhận xét trên, ta chỉ cần quản lý các thành phần liên thông có kích thước ít nhất là ~2~ đỉnh, và xử lý riêng các trường hợp thành phần liên thông chỉ có một đỉnh. Về mặt cài đặt, ta chỉ cần thêm đỉnh vào cấu trúc dữ liệu Disjoint Set Union khi ta cần gộp thành phần liên thông của đỉnh đó với đỉnh khác.

Độ Phức Tạp

• Ý tưởng trên có thể được cài đặt với độ phức tạp ~O(m \log m + k + m \log k \cdot \alpha(n))~. Giải thích:

  • Việc quản lý các thành phần liên thông giờ đây chỉ có độ phức tạp ~O(k)~ để khởi tạo và ~O(m)~ để thêm đỉnh khi xử lý tất cả ~m~ cạnh. Vì thế độ phức tạp tổng của cách cài đặt là ~O(m \log m) + O(k) + O(m) + O(m \log k \cdot \alpha(n)) = O(m \log m + k + m \log k \cdot \alpha(n))~

• Với cách cài đặt này, độ phức tạp bộ nhớ là ~O(m + k)~. Giải thích:

  • Lưu danh sách cạnh chiếm cần ~O(m)~ bộ nhớ như trong Subtask 1.
  • Lưu ~k~ cấu trúc dữ liệu Disjoint Set Union cần ~O(k)~ bộ nhớ và cần thêm ~O(m)~ bộ nhớ do chúng ta có thể thêm tối đa ~2 \cdot m~ đỉnh. ~\Rightarrow~ Độ phức tạp tổng của cách cài đặt là ~O(m) + O(m) + O(k) = O(m + k)~.

Code Minh Họa:

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int addVertex() {
        const int result = roots.size();
        roots.push_back(-1);
        return result;
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

class UndirectedGraph {
private:

    unordered_map<int, int> ids;
    DisjointSetUnion dsu;

public:

    bool checkConnected(const int x, const int y) const {
        const auto a = ids.find(x);
        if (a == ids.end())
            return false;
        const auto b = ids.find(y);
        if (b == ids.end())
            return false;
        return dsu.checkConnected(a -> second, b -> second);
    }

    int getID(const int x) {
        const auto a = ids.find(x);
        if (a == ids.end())
            return ids[x] = dsu.addVertex();
        return a -> second;
    }

    bool unite(const int x, const int y) {
        return dsu.unite(getID(x), getID(y));
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
long long result[MAX_K];
vector<UndirectedGraph> graphs;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    int low = 0, middle = 0, high = 0;

    graphs.resize(k + 1);

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges) {
        low = 0;
        high = k + 1;
        while (low + 1 < high) {
            middle = low + high >> 1;
            if (graphs[middle].checkConnected(u, v))
                low = middle;
            else
                high = middle;
        }
        if (high <= k) {
            graphs[high].unite(u, v);
            result[high] += w;
        }
    }

    for (int i = 1; i <= k; ++i)
        cout << result[i] << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #1

Coding Challenge #1 có tên là Đường đi. Đây là một bài toán về chủ đề đường đi ngắn nhất trên đồ thị, với điểm khác biệt là cách xây dựng tập cạnh thông qua các truy vấn nối và tô màu đỉnh.

Bài toán này chứng kiến 182 độc giả tham gia giải và 30 bài giải đạt điểm tuyệt đối. Đội ngũ Tạp chí VNOI xin phép chọn lọc ra 2 lời giải được các độc giả gửi về cho Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ Coding Challenge #1 - Đường đi

Cho một đồ thị vô hướng gồm ~N~ đỉnh, ban đầu đồ thị này không có cạnh nào. Mỗi đỉnh thứ ~i~ được gán một màu ~c_i~. Bạn cần thực hiện lần lượt ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Loại 1: 1 x y - nối toàn bộ các đỉnh có màu ~x~ với toàn bộ các đỉnh có màu ~y~.

• Loại 2: 2 u v - đổi màu của toàn bộ các đỉnh ~i~ có ~c_i = u~ thành ~c_i = v~.

Sau khi thực hiện xong tất cả các thao tác, hãy in ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, ..., c_N~ - màu ban đầu của từng đỉnh ~(1 \le c_i \le N)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~t, x, y~ mô tả các thao tác ~(1 \le t \le 2, 1 \le x, y \le N)~.

Output

• In ra ~N~ số nguyên, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~. Nếu không tồn tại đường đi, in ra ~-1~.

Scoring

Sample Input 1

5 4
1 2 3 2 1
1 1 2
2 3 2
1 2 3
1 1 3

Sample Output 1

0 1 -1 1 2

Notes

• Ban đầu: chưa có cạnh nào;

• Thao tác 1 1 2: Nối toàn bộ đỉnh màu ~1~ với toàn bộ đỉnh màu ~2~ ~\Rightarrow~ Tạo cạnh giữa các đỉnh ~{1, 5}~ với ~{2, 4}~;

• Thao tác 2 3 2: Đổi toàn bộ đỉnh màu ~3~ thành màu ~2~ ~\Rightarrow~ Đỉnh ~3~ có màu ~2~;

• Thao tác 1 2 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~;

• Thao tác 1 1 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~.

Sau cùng, đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh khác là:

• Đỉnh ~1~ ~\rightarrow~ chính nó: ~0~

• Đỉnh ~2~: ~1~ ~\rightarrow~ ~2~ (độ dài ~1~)

• Đỉnh ~3~: Không tồn tại đường đi (~-1~)

• Đỉnh ~4~: ~1~ ~\rightarrow~ ~4~ (độ dài ~1~)

• Đỉnh ~5~: ~1 \rightarrow 2 \rightarrow 5~ (độ dài ~2~)

Minh họa test ví dụ

Lời giải #1

Subtask 1

• Giới hạn bổ sung: ~N, Q \le 100~

Ý tưởng:

• Vì giới hạn của subtask này là nhỏ, chúng ta có thể giải quyết subtask này bằng cách thực hiện chính xác như những gì đề yêu cầu.

  • Với thao tác loại ~1~ với hai màu ~x~ và ~y~, chúng ta duyệt tuần tự để tìm tập các đỉnh có màu ~x~ và tập các đỉnh có màu ~y~ rồi với mỗi cặp đỉnh từ hai tập, ta thêm cạnh nối hai chiều giữa hai đỉnh.

  • Với thao tác loại ~2~ với hai màu ~u~ và ~v~, chúng ta duyệt tuần tự và gán màu ~v~ cho các đỉnh có màu ~u~

    ~ c[i] \leftarrow v \quad \forall \, (c[i] = u) ~

• Sau khi thực hiện xong tất cả các thao tác, để tìm ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị, ta có thể sử dụng thuật toán BFS từ đỉnh ~1~ trên đồ thị không trọng số dựng được.

Độ phức tạp:

• Cách giải như trên có độ phức tạp về thời gian là ~O(Q \cdot N^2)~ trong trường hợp xấu nhất

  • Quá trình đọc dữ liệu có độ phức tạp về thời gian là ~O(N + Q)~

  • Với mỗi thao tác loại ~1~, vì mỗi màu có ~O(N)~ đỉnh có màu đó, ta sẽ phải xem xét qua ~O(N^2)~ cặp đỉnh cho hai màu ~x~ và ~y~.

  • Với mỗi thao tác loại ~2~, ta phải quyệt qua ~O(N)~ đỉnh.

  • Bước chạy thuật toán BFS sẽ có độ phức tạp về thời gian là ~O(N + |E|)~ với ~|E|~ là số cạnh của đồ thị sau khi ta đã dựng xong. Vì dữ liệu có thể chứa ~O(Q)~ thao tác loại ~1~, ta có ~|E| = O(Q \cdot N^2)~. Nói cách khác, bước xử lý tìm đường đi ngắn nhất có độ phức tạp ~O(Q \cdot N^2)~

• Tương tự, độ phức tạp bộ nhớ của cách giải trên là ~O(Q \cdot N^2)~ trong trường hợp tệ nhất bởi ta phải lưu ~O(Q \cdot N^2)~ cạnh đồng thời cùng một lúc

Code minh họa:

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];

void addEdges(const int x, const int y) {
    for (int i = 1; i <= N; ++i) {
        if (c[i] != x)
            continue;
        for (int j = 1; j <= N; ++j) {
            if (c[j] != y)
                continue;
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }
}

void changeColors(const int u, const int v) {
    for (int i = 1; i <= N; ++i)
        if (c[i] == u)
            c[i] = v;
}

void runBFS() {
    queue<int> q;

    minimumDistance[1] = 0;
    q.push(1);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++i) {
        minimumDistance[i] = INF;
        cin >> c[i];
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (t == 1)
            addEdges(x, y);
        else
            changeColors(x, y);
    }

    runBFS();

    for (int i = 1; i <= N; ++i)
        cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';

    cout << '\n';

    return 0;
}