Hướng dẫn giải của Thi thử Duyên hải 2021 - Lần 1 - Bài 5 - RUNNING
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ả:
~\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