Hướng giải của Hành trình an toàn
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Lời giải
Dựng MST, sau đó DFS trên cây từ S đến T để tìm cạnh lớn nhất trên lộ trình.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
long long w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
struct DSU {
vector<int> parent;
DSU(int n) {
parent.resize(n + 1);
for (int i = 1; i <= n; i++) parent[i] = i;
}
int find(int v) {
if (v == parent[v]) return v;
return parent[v] = find(parent[v]);
}
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
parent[b] = a;
return true;
}
};
vector<vector<pair<int, long long>>> adj;
long long ans = -1;
int target;
bool dfs(int u, int p, long long max_w) {
if (u == target) {
ans = max_w;
return true;
}
for (auto& edge : adj[u]) {
int v = edge.first;
long long w = edge.second;
if (v != p) {
if (dfs(v, u, max(max_w, w))) return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
int s, t;
cin >> s >> t;
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
sort(edges.begin(), edges.end());
DSU dsu(n);
adj.resize(n + 1);
int edges_used = 0;
for (auto& e : edges) {
if (dsu.unite(e.u, e.v)) {
adj[e.u].push_back({e.v, e.w});
adj[e.v].push_back({e.u, e.w});
edges_used++;
if (edges_used == n - 1) break;
}
}
// Check connectivity in original graph first or via DSU
if (dsu.find(s) != dsu.find(t)) {
cout << -1 << "\n";
return 0;
}
target = t;
dfs(s, 0, 0);
cout << ans << "\n";
return 0;
}
Nhận xét