Hướng giải của Tỷ giá chênh lệch
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ả:
Đây là bài toán Arbitrage (mua bán chênh lệch tỷ giá tiền tệ).
Chúng ta muốn kiểm tra xem có chu trình nào mà tích các tỷ giá \(r_1 \cdot r_2 \dots r_k > 1\) hay không.
Bằng cách lấy log tự nhiên ở cả hai vế:
\(\ln(r_1) + \ln(r_2) + \dots + \ln(r_k) > 0\)
Nhân với \(-1\):
\(-\ln(r_1) - \ln(r_2) - \dots - \ln(r_k) < 0\)
Như vậy, ta gán trọng số mới cho mỗi cung dịch chuyển là \(w = -\ln(r)\) và cần tìm xem có bất kỳ chu trình âm nào trong đồ thị hay không.
Vì chu trình âm có thể nằm ở bất kỳ đâu, ta khởi tạo dist[i] = 0 cho mọi đỉnh \(i\) và chạy Bellman-Ford để phát hiện chu trình âm.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v;
double w;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
int u, v;
double r;
cin >> u >> v >> r;
edges[i] = {u, v, -log(r)};
}
// Đặt khoảng cách ban đầu bằng 0 cho tất cả các đỉnh
vector<double> dist(n + 1, 0.0);
for (int i = 1; i < n; i++) {
for (const auto& e : edges) {
if (dist[e.u] + e.w < dist[e.v]) {
dist[e.v] = dist[e.u] + e.w;
}
}
}
bool has_neg_cycle = false;
for (const auto& e : edges) {
if (dist[e.u] + e.w < dist[e.v] - 1e-9) {
has_neg_cycle = true;
break;
}
}
if (has_neg_cycle) cout << "YES\n";
else cout << "NO\n";
return 0;
}
Nhận xét