Editorial for Thi thử Duyên hải 2021 - Lần 1 - Bài 5 - RUNNING


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 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
*/

Comments

Please read the guidelines before commenting.


There are no comments at the moment.