Hướng dẫn giải của Thi thử Duyên hải 2021 - Lần 1 - Bài 5 - RUNNING


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: SPyofgame


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

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

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

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

~Fm~ 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~)

  • Ta có 3 cách đi

Đi từ ~s \rightarrow u \rightarrow t~ và ~s \rightarrow v \rightarrow t~ với ~u \in Fm~ và ~v \in (Fs \cap Ft)~

Đi từ ~s \rightarrow u \rightarrow t~ và ~s \rightarrow u \rightarrow v \rightarrow t~ với ~u \in Fm, v \in Ft~

Đi từ ~s \rightarrow u \rightarrow v \rightarrow t~ với ~u \in (Fs \cap Fm)~ và ~v \in (Ft \cap Fm)~


~\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à ~Fs~. Tương tự ta cũng có tập ~Ft~. Tập ~Fm = ~ {~1, 2, \dots, n~} \ (~Fs~ ~\cap~ ~Ft~ ~\cap~ {~s~} ~\cap~ {~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 Fm~ và ~v \in (Fs \cap Ft)~ ~\big)~

~II~: ~s \rightarrow u \rightarrow t~ và ~s \rightarrow u \rightarrow v \rightarrow t~ ~\ \ \ \ \ \ \ \ \ \ \big(~ ~u \in Fm~ và ~v \in Ft~ ~\big)~

~III~: ~s \rightarrow u \rightarrow v \rightarrow t~ ~\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \big(~ ~u \in (Fs \cap Fm)~ và ~v \in (Ft \cap Fm)~ ~\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ớ}}}}~

#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> Fs, Ft;
    dfs(Fs, s, t, s);
    dfs(Ft, t, s, t);

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

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

    // for (int m : Fm)             cout << m << ' '; cout << endl;
    // for (int u : Fs) if (u != s) cout << u << ' '; cout << endl;
    // for (int v : Ft) if (v != t) cout << v << ' '; cout << endl;

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

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

    int Ks = 0, Kt = 0;
    for (int u : Fm) maximize(Ks, min(ds[u], dt[u] + Vt));
    for (int v : Fm) 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.