Hướng dẫn cho Running (DHBB 2021 T.Thử)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

$\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}$

$\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}$

$\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}$

$\color{orange}{\text{Hướng dẫn}}$

Ta có 3 cách đi

Đi 2 đường phân biệt $s \rightarrow u$, $t \rightarrow v$ (2 đường không cắt nhau). Sau đó ta chỉ cân kẻ một đường từ $u \rightarrow v$

Đi thằng tử $s \rightarrow t$ và đi thêm 2 đường phân biệt $s \rightarrow u$, $t \rightarrow v$ (3 đường không cắt nhau). Sau đó ta chỉ cân kẻ một đường từ $u \rightarrow v$

Đi từ $s \rightarrow u$ và đi thêm 2 đường phân biệt $u \rightarrow t$, $t \rightarrow v$ (3 đường không cắt nhau). Sau đó ta chỉ cân kẻ một đường từ $u \rightarrow v$

Chia các đỉnh thành 3 tập

$F_s$ là tập các đỉnh kề $s$ và không thể đến $t$ mà không đi qua $s$

$F_t$ là tập các đỉnh kề $t$ và không thể đến $s$ mà không đi qua $t$

$F_m$ là tập các đỉnh kề $s$ và cả $t$, đi đến cả $s$ (hay $t$) mà không cần đi qua $t$ (hay $s$)

Khi đó ta có

Đi từ $s \rightarrow u \rightarrow t$ và $s \rightarrow v \rightarrow t$ với $u \in F_m$ và $v \in (F_s \cup F_t)$

Đi từ $s \rightarrow u \rightarrow t$ và $s \rightarrow u \rightarrow v \rightarrow t$ với $u \in F_m, v \in F_t$

Đi từ $s \rightarrow u \rightarrow v \rightarrow t$ với $u \in (F_s \cup F_m)$ và $v \in (F_t \cup F_m)$

$\color{goldenrod}{\text{Tiếp cận}}$

Đầu tiên ta $bfs$ để tính $d_s[]$ và $d_t[]$ với $d_u[v]$ là đường đi ngắn nhất từ $u \rightarrow v$
Sau đó ta $dfs$ để lấy tất cả các đỉnh xuất phát từ $s$ nhưng không đi đến $t$, gọi tập này là $F_s$. Tương tự ta cũng có tập $F_t$. Tập $F_m = $ {$1, 2, \dots, n$} \ ($F_s$ $\cup$ $F_t$ $\cup$ {$s$} $\cup$ {$t$})
Lưu ý:

Khi $bfs$: không cần sài dijkstra vì đồ thị có dạng cây

Khi $dfs$: nhớ sài tham trị để không tăng độ phức tạp

Ta có 3 cách đi:

$I$: $s \rightarrow u \rightarrow t$ và $s \rightarrow v \rightarrow t$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \big($ $u \in F_m$ và $v \in (F_s \cup F_t)$ $\big)$

$II$: $s \rightarrow u \rightarrow t$ và $s \rightarrow u \rightarrow v \rightarrow t$ $\ \ \ \ \ \ \ \ \ \ \big($ $u \in F_m$ và $v \in F_t$ $\big)$

$III$: $s \rightarrow u \rightarrow v \rightarrow t$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \big($ $u \in (F_s \cup F_m)$ và $v \in (F_t \cup F_m)$ $\big)$

Các cách đi khác cắt nhau sẽ bị giảm giá trị bằng min của cả 2 cách nên không tối ưu

Lưu ý rằng tuy cả 3 cách trên các đương đi đều không cắt nhau, nhưng riêng cách $II$ thì số lượng từ $s$ (hoặc $t$) đến $u$ có thể ít hơn tổng số lượng đến $t$ (hoặc $s$) và $v$ cộng lại

Ta định nghĩa các giá trị

$V_s = max(s \rightarrow u\ \ |\ \ u \in F_s)$

$V_t = max(t \rightarrow v\ \ |\ \ v \in F_t)$

$M_s = max(s \rightarrow u\ \ |\ \ u \in F_m)$

$M_t = max(t \rightarrow v\ \ |\ \ v \in F_m)$

$K_s = max(min(s \rightarrow u, u \rightarrow t + V_t)\ \ |\ \ u \in F_m)$

$K_t = max(min(t \rightarrow v, v \rightarrow s + V_s)\ \ |\ \ v \in F_m)$

Giá trị của 3 hướng đi là

$I = (s \rightarrow t) + min(V_s, V_t) = (t \rightarrow s) + min(V_s, V_t)$

$II = max(K_s, K_t)$

$III = min(M_s + M_t, M_s + V_t, V_s + M_t, V_s + V_t)$

Kết quả bài toán là $res = max(I, II, III)$

$\color{purple}{\text{Độ phức tạp}}$

Việc $dfs()$ và $bfs()$ có thể hoàn thành trong $O(n + m)$, mà vì đồ thị cây nên $m = n - 1 \Rightarrow O(n)$
Việc tính kết quả có thể hoàn thiện trong $O(|F_s| + |F_t| + 4 \times |F_m| + O(1)) = O(n)$
Vậy thuật dưới đây là tuyến tính $O(n)$ cả về thời gian lẫn bộ nhớ

$\color{green}{\text{Code tham khảo }}$: dfs, bfs, toán học, đồ thị

$^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}$

C++

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

const int LIM = 1e5 + 15;
const int INF = 0x3f3f3f3f;

struct Node
{
    int u, d;
    Node (int u = 0, int d = 0)
    : u(u), d(d) {}

    bool operator < (const Node &o) const
    {
        return d > o.d;
    }
};

int n, m, s, t;
vector<Node> G[LIM];
void input()
{
    cin >> n >> s >> t;
    m = n - 1;
    for (int i = 1; i <= m; ++i)
    {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Node(v, w));
        G[v].push_back(Node(u, w));
    }
}

void bfs(int s, vector<int> &d)
{
    d.assign(n + 1, 0);
    d[s] = +INF;

    deque<int> S;
    S.push_back(s);

    while (S.size())
    {
        int u = S.front();
        S.pop_front();

        for (const Node &e : G[u])
        {
            int v = e.u;
            int w = e.d;
            if (d[v] == 0)
            {
                d[v] = min(d[u], w);
                S.push_back(v);
            }
        }
    }
}

bool dfs(vector<int> &S, int s, int t, int u, int p = -1)
{
    if (u == t) return true;
    S.push_back(u);

    vector<vector<int> > T;
    for (const Node &e : G[u])
    {
        int v = e.u;
        if (v != p)
        {
            T.resize(T.size() + 1);
            if (dfs(T.back(), s, t, v, u))
            {
                T.pop_back();
                if (u != s) return true;
            }
        }
    }

    if (T.empty()) return false;

    int pos = 0;
    for (int i = 1; i < T.size(); ++i)
        if (T[pos].size() < T[i].size())
            pos = i;

    swap(S, T[pos]);
    for (int i = 0; i < T.size(); ++i)
        for (int x : T[i])
            S.push_back(x);

    return false;
}

int solve()
{
    vector<int> ds, dt;
    bfs(s, ds);
    bfs(t, dt);

    vector<int> F_s, F_t;
    dfs(F_s, s, t, s);
    dfs(F_t, t, s, t);

    vector<int> used(n + 1, false);
    for (int u : F_s) used[u] = true;
    for (int v : F_t) used[v] = true;
    used[s] = used[t] = true;

    vector<int> F_m;
    for (int m = 1; m <= n; ++m)
        if (used[m] == false)
            F_m.push_back(m);

    // for (int m : F_m)             cout << m << ' '; cout << endl;
    // for (int u : F_s) if (u != s) cout << u << ' '; cout << endl;
    // for (int v : F_t) if (v != t) cout << v << ' '; cout << endl;

    int Vs = 0, Vt = 0;
    for (int u : F_s) if (u != s) maximize(Vs, ds[u]);
    for (int v : F_t) if (v != t) maximize(Vt, dt[v]);
    int two_ways = ds[t] + min(Vs, Vt);

    int Ms = 0, Mt = 0;
    for (int m : F_m) maximize(Ms, ds[m]);
    for (int m : F_m) maximize(Mt, dt[m]);
    int one_way = min(max(Ms, Vs), max(Mt, Vt));

    int Ks = 0, Kt = 0;
    for (int u : F_m) maximize(Ks, min(ds[u], dt[u] + Vt));
    for (int v : F_m) maximize(Kt, min(dt[v], ds[v] + Vs));
    int one_two = max(Ks, Kt);

    // cout << one_way << ' ' << two_ways << endl;
    return max(max(two_ways, one_way), one_two);
}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    input();
    cout << solve();
    return 0;
}

/*
6 1 4
1 5 15
1 2 10
1 4 10
4 6 10
3 4 5

5
|
|
|15
|
|    10
1----------2
|
|
|10
|
|
4----------3
|    5
|
|10
|
|
6

ds[t] = 1-4 = 10
min(Vs, Vt) = 1-5-6-4 = 10
*/

/*
18 1 4
1 2 11
1 5 10
1 17 5
1 18 15
3 4 5
4 6 15
4 7 20
6 15 15
6 16 10
7 8 25
7 9 5
7 18 5
8 11 5
9 10 5
10 12 5
10 13 5
10 14 25

            5
            |
            |
            |10
            |
    5     |    11
17----------1----------2
            |
            |
            |15
            |
            |
            18                   13
    5     |                     |
            |                     |
            |5                    |5
            |                     |
    25    |     5          5    |     25
8----------7----------9----------10----------14
|          |                     |
|          |                     |
|5         |20                   |5
|          |                     |
|          |                     |
11         4----------3          12
            |     5
            |
            |15
            |
            |
16----------6----------15
    10          15

one_way  = 1-18-7-4 = 15
two_ways = 1-18-7-4 + 1-2-6-4 = 5 + 11
*/

/*
4 1 4
1 2 100
2 4 10
3 4 20

    100
2------------1
|
|
|10
|
|
4------------3
    20

one_two = 30
*/

Bình luận

Không có bình luận nào.

Hướng dẫn cho Running (DHBB 2021 T.Thử)

\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

\(\color{goldenrod}{\text{Tiếp cận}}\)

\(\color{purple}{\text{Độ phức tạp}}\)

\(\color{green}{\text{Code tham khảo }}\): dfs, bfs, toán học, đồ thị

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

Bình luận