Bài toán đường đi ngắn nhất (phần 2) - Thuật toán Dijkstra và Ford Bellman
Đây là bài viết số 2 trong series bài viết về Bài toán đường đi ngắn nhất trên đồ thị. Để theo dõi lại phần 1 của series, các bạn hãy nhấn vào đây.
I. Tổng quan
1. Phát biểu bài toán
Ta đã biết về thuật toán Floyd - Warshall trong bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh trước đây. Thuật toán hoạt động rất hiệu quả trong các bài toán cần xác định nhanh đường đi ngắn nhất giữa hai đỉnh bất kì, tuy nhiên nhược điểm của nó là độ phức tạp khá lớn lên tới vì vậy chỉ có thể sử dụng trên các đồ thị có số đỉnh vừa phải.
Trên thực tế, không phải lúc nào ta cũng cần tìm ra đường đi ngắn nhất giữa mọi cặp đỉnh. Bài toán đường đi ngắn nhất xuất phát từ một đỉnh (single-source shortest path) là một bài toán rất thông dụng như vậy, bài toán của giải thuật Floyd chỉ là dạng biến đổi của nó mà thôi. Bài toán này được phát biểu như sau:
Cho đơn đồ thị có hướng, có trọng số các đỉnh được đánh số từ tới . Độ dài của đường đi ngắn nhất giữa hai đỉnh và được kí hiệu là và nếu như không tồn tại đường đi từ đỉnh tới một đỉnh nào đó thì ta sẽ coi .
Yêu cầu: Hãy tìm các đường đi ngắn nhất từ một đỉnh xuất phát cho trước tới một đỉnh cho trước trên đồ thị?
Input:
- Dòng đầu tiên chứa hai số nguyên dương và - số đỉnh và số cạnh của đồ thị.
- Dòng thứ hai chứa hai số nguyên dương và - hai đỉnh xuất phát và đỉnh đích cần tìm đường đi ngắn nhất.
- Trên dòng tiếp theo, mỗi dòng chứa ba số nguyên dương - thể hiện một cung nối từ đỉnh tới đỉnh trên đồ thị có trọng số là .
Ràng buộc:
- .
- .
- .
Output:
- Dòng thứ nhất in ra độ dài đường đi ngắn nhất giữa hai đỉnh và . Nếu không tồn tại đường đi thì in ra .
- Dòng thứ hai in ra các đỉnh trên đường đi ngắn nhất từ tới nếu tồn tại, các đỉnh phân tách nhau bởi dấu cách.
Sample Input:
6 7 1 4 1 2 1 1 6 20 2 3 2 3 6 3 3 4 20 5 4 5 6 5 4
Sample Output:
15 1 2 3 6 5 4
Bài toán trên thực tế sẽ phải quy về việc tìm đường đi ngắn nhất từ đỉnh tới tất cả các đỉnh còn lại. Trong bài viết này, tôi sẽ giới thiệu tới các bạn một số thuật toán thông dụng để giải bài toán này, đó là Dijkstra và Ford Bellman. Ta quy ước các giải thuật sẽ được cài đặt trên đơn đồ thị có hướng. Trong trường hợp đồ thị là vô hướng ta vẫn quy được về đồ thị có hướng bằng cách coi mỗi cạnh là hai cung ngược chiều nhau.
2. Cấu trúc bài toán con tối ưu
Các thuật toán tìm đường đi ngắn nhất mà chúng ta sẽ khảo sát trong bài viết này đều dựa trên một đặc tính chung: Mỗi đoạn đường trên đường đi ngắn nhất phải là một đường đi ngắn nhất.
Ta có định lý sau:
Định lý 1.1: Cho đồ thị có trọng số gọi là một đường đi ngắn nhất từ tới . Khi đó đoạn đường là một đường đi ngắn nhất từ tới .
Bởi tính chất bài toán con tối ưu nói trên, hầu hết các thuật toán tìm đường đi ngắn nhất đều là thuật toán Quy hoạch động (ví dụ như Floyd) hoặc Tham lam (ví dụ như Dijkstra).
Nếu như đồ thị có chu trình âm (chu trình với độ dài âm) thì khoảng cách giữa một số cặp đỉnh nào đó có thể không xác định, bởi vì bằng cách đi vòng theo chu trình này một số lần đủ lớn, ta có thể chỉ ra đường đi giữa hai đỉnh nào đó trong chu trình này nhỏ hơn bất kỳ một số cho trước nào. Trong trường hợp như vậy, bài toán có thể quy về tìm đường đi đơn ngắn nhất, tuy nhiên hiện nay vẫn chưa ai tìm được một thuật toán tìm đường đi đơn ngắn nhất trên đồ thị có chu trình âm. Vì vậy, trong phạm vi bài viết này, ta sẽ xét các thuật toán tìm đường đi ngắn nhất trên đồ thị không có chu trình âm.
II. Thuật toán Ford Bellman - Đồ thị không có chu trình âm
1. Ý tưởng
Trên đơn đồ thị có hướng không có chu trình âm, thuật toán Ford Bellman có ý tưởng rất đơn giản như sau: Với đỉnh xuất phát gọi là độ dài đường đi ngắn nhất từ tới . Ban đầu ta khởi tạo:
- .
- .
Các sẽ lần lượt được tối ưu hóa như sau: Xét mọi cặp đỉnh của đồ thị, nếu như có một cặp đỉnh mà và thì ta gán lại:
Tức là, nếu độ dài đường đi từ tới hiện tại bị lớn hơn độ dài đường đi từ tới cộng với trọng số đi từ tới thì ta sẽ hủy bỏ đường đi cũ và coi đường đi mới từ tới chính là đường đi từ tới rồi từ tới . Thuật toán sẽ kết thúc khi không thể tối ưu thêm bất kì một giá trị nào nữa.
fill(d + 1, d + n + 1, inf);
bool stop = false;
while (!stop)
{
stop = true;
for (int u = 1; u <= n; ++u)
for (int v kề u)
if (d[v] > d[u] + w(u, v))
{
d[v] = d[u] + w(u, v);
stop = false;
}
}
Chứng minh: Tại bước khởi tạo, mỗi chính là độ dài ngắn nhất của đường đi từ tới đi qua không quá cạnh.
Giả sử tại bước lặp thứ đã bằng độ dài ngắn nhất đi từ tới qua không quá cạnh. Đường đi từ tới qua không quá cạnh sẽ được thành lập bằng cách: Lấy một đường đi từ tới một đỉnh nào đó kề với (qua không quá cạnh), rồi đi tiếp tới bằng cung trực tiếp do đó đường đi ngắn nhất từ tới qua không quá cạnh sẽ được tính bằng giá trị nhỏ nhất trong hai giá trị dưới đây (nguyên lí tối ưu Bellman):
- Độ dài đường đi ngắn nhất từ tới qua không quá cạnh (ở bước trước).
- Độ dài đường đi ngắn nhất từ tới (qua không quá cạnh) cộng với trọng số cung .
Vì vậy, sau mỗi bước lặp, được tối ưu bằng công thức:
Sau bước lặp thứ ta có bằng độ dài đường đi ngắn nhất từ tới qua không quá cạnh. Vì đồ thị không có chu trình âm, do đó sẽ có một đường đi ngắn nhất từ tới là đường đi cơ bản (đi qua không quá cạnh, do đường đi cơ bản là đường đi không có đỉnh lặp lại, mà đồ thị có đỉnh thì cần đi qua tối đa cạnh để đạt được đường đi cơ bản). Tức là sẽ là độ dài đường đi ngắn nhất từ tới hay nói cách khác, số bước lặp để tối ưu hóa sẽ không vượt quá bước.
Muốn truy vết lại đường đi ngắn nhất, ta sử dụng mảng để lưu lại đỉnh liền trước trong đường đi ngắn nhất từ tới . Mỗi khi cập nhật lại một thì đồng thời cập nhật lại đỉnh liền trước trên đường đi tối ưu sẽ là và gán luôn:
Thuật toán cũng có thể được cải tiến để xác định được đồ thị có tồn tại chu trình âm hay không theo ý tưởng sau:
- Sau khi xác định xong mọi xét lại các cung của đồ thị.
- Nếu như vẫn tồn tại một cung khiến cho nào đó có thể tối ưu hóa hơn nữa thì đồ thị sẽ có chu trình âm. Khi đó kết luận không thể tồn tại đường đi ngắn nhất từ tới .
2. Cài đặt
Danh sách cạnh là phương pháp tốt nhất để biểu diễn đồ thị trong thuật toán Ford Bellman.
Giá trị sẽ được gán bằng một hằng số thật lớn trong khi lập trình, ở đây tác giả lựa chọn giá trị .
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18;
struct edge
{
int u, v, w;
};
bool check_negative_cycle(int m, vector < edge > &edges_list, vector < int > &d)
{
// Nếu vẫn tồn tại cung (u -> v) mà d[v] có thể tối ưu hóa được thêm thì
// đồ thị sẽ tồn tại chu trình âm, trả về true cho hàm.
for (int i = 1; i <= m; ++i)
{
int u = edges_list[i].u, v = edges_list[i].v, w = edges_list[i].w;
if (d[u] != inf && d[u] + w < d[v])
return true;
}
return false;
}
void print_result(int s, int t, vector < int > &d, vector < int > &trace)
{
cout << d[t] << '\n';
vector < int > path;
while (t != s)
{
path.push_back(t);
t = trace[t];
}
path.push_back(s);
reverse(path.begin(), path.end());
for (int u: path)
cout << u << ' ';
}
void bellman_ford(int n, int m, int s, int t, vector < edge > &edges_list)
{
vector < int > d(n + 1, inf);
vector < int > trace(n + 1);
d[s] = 0;
// Lặp tối đa n - 1 lần.
for (int step = 1; step <= n - 1; ++step)
{
bool stop = true;
for (int i = 1; i <= m; ++i)
{
int u = edges_list[i].u, v = edges_list[i].v, w = edges_list[i].w;
if (d[u] != inf && d[u] + w < d[v])
{
d[v] = d[u] + w;
trace[v] = u;
stop = false;
}
}
// Nếu không thể tối ưu d[v] nào nữa thì dừng thuật toán.
if (stop) break;
}
// Nếu đồ thị có chu trình âm hoặc d[t] = oo thì không tìm được đường đi.
// Ngược lại truy vết đường đi từ s tới t.
if (check_negative_cycle(m, edges_list, d) || d[t] == inf)
cout << -1;
else
print_result(s, t, d, trace);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
vector < edge > edges_list(m + 1);
for (int i = 1; i <= m; ++i)
cin >> edges_list[i].u >> edges_list[i].v >> edges_list[i].w;
bellman_ford(n, m, s, t, edges_list);
return 0;
}
Trong trường hợp đề bài yêu cầu tìm ra một chu trình âm gặp phải trên đường đi từ ta có thể thực hiện thêm một số bước dưới đây:
- Bước 1: Tìm ra đỉnh mà vẫn còn có thể tối ưu thêm sau khi đã thực hiện giải thuật Ford Bellman lần. Đây chính là một đỉnh nằm trong chu trình âm.
- Bước 2: Tìm ra đỉnh đầu tiên thuộc chu trình âm mà từ tới được nó, bằng cách đi ngược lại đủ lần.
- Bước 3: Từ đỉnh tìm ra các đỉnh thuộc chu trình âm chứa bằng cách liên tục ghi nhận rồi đi ngược về tới khi quay lại đỉnh ở bước tìm được.
Đoạn chương trình kiểm tra chu trình âm có thể điều chỉnh như sau để thu được các đỉnh thuộc chu trình âm:
void check_negative_cycle(int m, vector < edge > &edges_list, vector < int > &d,
vector < int > &trace)
{
int x = -1;
for (int i = 1; i <= m; ++i)
{
int u = edges_list[i].u, v = edges_list[i].v, w = edges_list[i].w;
if (d[u] != inf && d[u] + w < d[v])
{
d[v] = d[u] + w;
trace[v] = u;
x = v;
}
}
// Tìm thấy chu trình âm.
if (x != -1)
{
// Tìm đỉnh xuất phát của chu trình âm, tức là đỉnh đầu tiên
// thuộc chu trình âm mà từ s tới đuợc nó.
for (int i = 1; i <= n; ++i)
x = trace[x];
// Tìm ra các đỉnh thuộc chu trình âm.
vector < int > negative_cycle;
for (int y = x; ; y = trace[y])
{
negative_cycle.push_back(y);
if (y == x && negative_cycle.size() > 1)
break;
}
reverse(negative_cycle.begin(), negative_cycle.end());
// In chu trình âm.
for (int u: negative_cycle)
cout << u << ' ';
}
}
3. Đánh giá
Về mặt bộ nhớ, do sử dụng danh sách cạnh để biểu diễn đồ thị nên độ phức tạp bộ nhớ của thuật toán là .
Về mặt thời gian, dễ thấy thuật toán lặp không quá lần, và mỗi lần phải lặp qua cả cạnh để tối ưu các . Vì thế độ phức tạp tính toán tổng quát là .
III. Thuật toán Dijkstra - Đồ thị có trọng số trên các cung không âm
1. Giải thuật cơ bản
Ý tưởng
Trong trường hợp đồ thị có trọng số trên các cung không âm, thuật toán Dijkstra là một thuật toán hoạt động hiệu quả hơn rất nhiều so với Ford Bellman. Thuật toán Ford Bellman mặc dù giải quyết được bài toán trong trường hợp tổng quát, nhưng tồn đọng sự bất tiện sau đây:
Với mỗi đỉnh đặt là độ dài đường đi ngắn nhất từ tới . Thuật toán Ford Bellman khởi tạo và rồi tối ưu hóa dần các giá trị theo công thức: . Như vậy, nếu ta dùng một đỉnh để tối ưu hóa đỉnh và sau đó ở một bước nào đấy lại được tối ưu thêm, thì mọi liên quan tới ở bước trước đó đều sẽ phải sửa lại, dẫn tới việc sửa đi sửa lại nhiều lần.
Thuật toán Dijkstra có ý tưởng là thay vì duyệt lại mọi cung để tối ưu hóa ta sẽ chọn ngay một đỉnh mà không thể tối ưu thêm nữa rồi dùng nó để tối ưu hóa các đỉnh kề với nó. Đỉnh được chọn này sẽ là đỉnh có nhỏ nhất hiện tại. Như vậy, thuật toán có thể mô tả như sau:
- Bước 1: Khởi tạo Với đỉnh gọi là độ dài đường đi ngắn nhất từ tới . Ban đầu khởi gán và . Mỗi đỉnh sẽ có hai trạng thái: Còn có thể tối ưu tiếp hoặc không thể tối ưu hơn, được thể hiện bởi mảng hoặc tùy theo còn có thể tối ưu tiếp hoặc không. Ban đầu ta có .
- Bước 2: Lặp và tính toán
Bước này gồm hai thao tác được liên tục lặp lại tới khi đỉnh đích được cố định, hoặc tất cả các đỉnh còn có thể tối ưu tiếp lại đều có (tức là không tồn tại đường đi):
- Cố định nhãn: Chọn trong các đỉnh còn có thể tối ưu tiếp, lấy ra đỉnh có nhỏ nhất, rồi đánh dấu nó là không thể tối ưu hơn được nữa.
- Sửa nhãn: Dùng đỉnh vừa lấy ra, xét tất cả đỉnh kề với nó và sửa lại giá trị theo công thức:
- Bước 3: In kết quả Kết hợp với việc lưu vết đường đi trong quá trình cập nhật các thông báo đường đi ngắn nhất tìm được hoặc cho biết không tồn tại đường đi (nếu ).
Chứng minh:
Tại sao ở mỗi bước lặp, đỉnh với nhỏ nhất lại được chọn để cố định và tối ưu các đỉnh xung quanh nó?
Ta sử dụng phương pháp phản chứng: Giả sử đỉnh như vậy vẫn còn có thể tối ưu thêm, thì phải tồn tại một đỉnh nào đó với sao cho . Do trọng số không âm nên chắc chắn điều này trái với cách chọn là nhỏ nhất lúc đầu.
Vậy đỉnh với nhỏ nhất tất nhiên phải là đỉnh không thể tối ưu được thêm nữa.
Việc truy vết có thể thực hiện tương tự như trong giải thuật Ford Bellman, với là đỉnh liền trước trên đường đi ngắn nhất từ tới . Mỗi khi cập nhật một giá trị thì đồng thời cập nhật luôn .
Cài đặt
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 1, inf = 1e18;
vector < pair < int, int > > adj[maxn];
void print_result(int s, int t, vector < int > &d, vector < int > &trace)
{
if (d[t] == inf)
cout << -1;
else
{
cout << d[t] << '\n';
vector < int > path;
while (t != s)
{
path.push_back(t);
t = trace[t];
}
path.push_back(s);
reverse(path.begin(), path.end());
for (int v: path)
cout << v << ' ';
}
}
void dijkstra(int n, int m, int s, int t)
{
vector < int > d(n + 1, inf);
vector < bool > is_free(n + 1, true);
vector < int > trace(n + 1);
d[s] = 0;
while (true)
{
int u = 0;
for (int v = 1; v <= n; ++v)
if (d[v] < d[u])
u = v;
if (u == 0)
break;
for (auto e: adj[u])
{
int v = e.first, w = e.second;
if (is_free[v] && d[v] > d[u] + w)
{
d[v] = d[u] + w;
trace[v] = u;
}
}
}
print_result(s, t, d, trace);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
dijkstra(n, m, s, t);
return 0;
}
Đánh giá
Độ phức tạp bộ nhớ khi sử dụng danh sách kề để biểu diễn đồ thị sẽ là .
Trong trường hợp xấu nhất, thuật toán đơn giản này sẽ cần lần cố định các và mất thêm để tìm đỉnh ra đỉnh có nhỏ nhất. Vì thế thuật toán có độ phức tạp tính toán tổng quát là là .
2. Cải tiến với cấu trúc Heap
Ý tưởng
Với những đồ thị có khoảng trên đỉnh, giải thuật ở trên sẽ không thể đáp ứng được yêu cầu về thời gian thực thi. Giải pháp là cải tiến việc tìm ra đỉnh có nhỏ nhất, thông qua cấu trúc dữ liệu Heap (mà trong C++ đã cài đặt sẵn dưới dạng hàng đợi ưu tiên - priority_queue
):
- Khởi tạo một hàng đợi ưu tiên dạng
pair < int, int >
, trong đó mỗi phần tử sẽ lưu một đỉnh vẫn còn có thể tối ưu tiếp kèm theo giá trị hiện tại của nó. - Phần tử với nhỏ nhất sẽ được đưa lên đầu hàng đợi. Ban đầu trong hàng đợi ưu tiên chỉ có phần tử (đỉnh xuất phát cùng với nhãn bằng của nó).
Thuật toán diễn ra thông qua các bước lặp trên hàng đợi ưu tiên cho tới khi hàng đợi rỗng, hoặc phần tử chứa được đưa lên đầu hàng đợi (tức là đường đi tới đỉnh đã được tối ưu):
- Bước 1: Lấy ra đỉnh ở đầu hàng đợi, đỉnh này chính là đỉnh có không thể tối ưu được nữa (và là nhỏ nhất). Đánh dấu nó là không thể tối ưu được nữa (gán ) rồi xóa khỏi hàng đợi ưu tiên.
- Bước 2: Sử dụng đỉnh tối ưu các đỉnh kề với nó mà có theo công thức: sau đó đưa phần tử vào hàng đợi ưu tiên.
Cài đặt
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair < int, int > pi;
const int maxn = 1e5 + 1, inf = 1e18;
vector < pair < int, int > > adj[maxn];
void print_result(int s, int t, vector < int > &d, vector < int > &trace)
{
if (d[t] == inf)
cout << -1;
else
{
cout << d[t] << '\n';
vector < int > path;
while (t != s)
{
path.push_back(t);
t = trace[t];
}
path.push_back(s);
reverse(path.begin(), path.end());
for (int v: path)
cout << v << ' ';
}
}
void dijkstra_heap(int n, int m, int s, int t)
{
vector < int > d(n + 1, inf);
vector < bool > is_free(n + 1, true);
vector < int > trace(n + 1);
priority_queue < pi, vector < pi >, greater < pi > > qu_min;
d[s] = 0;
qu_min.push({d[s], s});
while (!qu_min.empty())
{
int u = qu_min.top().second;
int du = qu_min.top().first;
qu_min.pop();
if (u == t)
break;
is_free[u] = false;
for (auto e: adj[u])
{
int v = e.first, w = e.second;
if (is_free[v] && d[v] > du + w)
{
d[v] = du + w;
trace[v] = u;
qu_min.push({d[v], v});
}
}
}
print_result(s, t, d, trace);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
}
dijkstra_heap(n, m, s, t);
return 0;
}
Đánh giá
Với việc sử dụng danh sách kề, độ phức tạp về bộ nhớ của thuật toán chỉ là .
Về độ phức tạp tính toán, do việc áp dụng priority_queue
để tìm ra đỉnh tốt nhất ở mỗi bước, nên độ phức tạp tổng quát của thuật toán là .
IV. Bài tập áp dụng
1. Cai trị vương quốc
Đề bài (Tóm tắt)
Nhà vua của một vương quốc nọ là người không thông minh cho lắm, ông ta chỉ có thể làm được các phép tính cộng, so sánh lớn hơn (>
) và nhỏ hơn (<
) với một số nguyên cho trước, cũng như tính tổng một dãy con liên tiếp trong một dãy số cho trước. Vì vậy, các vấn đề khi trình lên nhà vua để nhận quyết định đều được mô tả bằng một dãy số nguyên, sau đó nhà vua sẽ đưa ra quyết định bằng cách ra thông báo rằng tổng của dãy số đó lớn hơn hay nhỏ hơn một số nguyên nào đó.
Ngày nọ, một nhóm những kẻ chống đối trình lên nhà vua một vấn đề lớn dưới dạng một dãy số nguyên sau đó xin quyết định của nhà vua cho vấn đề nhỏ dưới dạng một dãy con S_i = \{a_{s_i}, a_{s_i + 1}, \dots, a_{s_i + n_i\} \ (1 \le i \le m) thuộc dãy . Nhà vua đã đưa ra quyết định nhanh chóng: Với mỗi dãy con ngài đưa ra một số nguyên rồi thông báo tổng của dãy con lớn hơn hoặc nhỏ hơn - đó chính là quyết định của ngài. Rồi như thường lệ, nhà vua lãng quên dãy số ban đầu đã nhận được.
Tuy nhiên, nhà vua đã rơi vào âm mưu của những kẻ chống đối! Chúng đã tìm ra những sai sót trong quyết định của nhà vua và vin vào đó để tổ chức những cuộc biểu tình, hòng bắt ép nhà vua thoái vị. Nhận được tin báo, nhà vua rất lo lắng vì ngài đã quên mất dãy số ban đầu mình nhận được. Vì vậy, nhà vua quyết định đưa ra một dãy giả mạo sao cho nó thỏa mãn tất cả các quyết định mà ngài đã đưa ra, rồi tuyên bố rằng đó chính là vấn đề ban đầu mà mình nhận được.
Yêu cầu: Hãy xác định xem nhà vua có thể tìm ra dãy giả mạo thỏa mãn tất cả những quyết định mà ngài đã đưa ra hay không?
Input:
- Gồm nhiều test cases, mỗi test case gồm một nhóm dòng có cấu trúc như sau:
- Dòng đầu tiên chứa hai số nguyên dương - độ dài của dãy nhà vua nhận được và số lượng quyết định nhà vua đã đưa ra.
- Trên dòng tiếp theo, mỗi dòng chứa một bộ bốn giá trị - với là
gt
thể hiện cho phép so sánh>
hoặclt
thể hiện cho phép so sánh<
. Đây là một quyết định của nhà vua cho biết dãy con có tổng lớn hơn hoặc nhỏ hơn giá trị theo thể hiện của .
- Dòng cuối cùng của đầu vào chứa duy nhất số - thể hiện kết thúc việc nhập dữ liệu.
Ràng buộc:
- .
- .
Output:
- Ứng với mỗi test case, in ra
successful conspiracy
nếu như nhà vua không thể tìm ra một dãy giả mạo phù hợp, ngược lại in ralamentable kingdom
. Kết quả của mỗi test case được in ra trên một dòng.
Sample Input:
4 2
1 2 gt 0
2 2 lt 2
1 2
1 0 gt 0
1 0 lt 0
0
Sample Output:
lamentable kingdom
successful conspiracy
Ý tưởng
Cai Trị Vương Quốc - Editorial
Xét hàm và coi .
Gọi tổng của dãy con là . Từ tính chất tổng tiền tố, ta biết rằng . Khi đó, quyết định thứ của nhà vua sẽ tương ứng với:
Như vậy, một dãy số thỏa mãn tất cả các quyết định của nhà vua sẽ tồn tại khi và chỉ khi tồn tại một dãy các giá trị thỏa mãn điều kiện với mọi .
Ta lại biến đổi một chút ở các điều kiện:
-
Với điều kiện nó tương đương với và tương tự, tương đương với .
-
Áp dụng biến đổi trên vào dãy điều kiện với mọi ta có một dãy các ràng buộc ở dạng:
Cụ thể hơn, nếu như thì ta đưa nó về ngược lại thì đưa về . Ở đây và .
Dãy các ràng buộc như trên được gọi là "Hệ thống các ràng buộc khác nhau (System of difference constraints)" - một mô hình toán học sử dụng rất rộng rãi trong khoa học máy tính, và được giải quyết thông qua phương pháp xây dựng "Đồ thị ràng buộc". Trên đồ thị này, các đỉnh được đánh số từ tới và mỗi điều kiện được thể hiện bởi một cung nối từ đỉnh tới đỉnh trên đồ thị (hoặc ngược lại) với trọng số là . Riêng đỉnh (đỉnh đặc biệt) sẽ có cung nối tới tất cả các đỉnh còn lại với trọng số là .
Sau khi xây dựng đồ thị, nếu như đồ thị không có chu trình âm và tất cả các đều là số nguyên thì sẽ tồn tại một đáp án số nguyên phù hợp với tất cả các ràng buộc, ngược lại thì không có đáp án nào cả (tức là không tồn tại dãy số thỏa mãn).
Ta có thể sử dụng thuật toán Ford Bellman để giải quyết bài toán trên. Tuy nhiên, đỉnh đặc biệt trong bài toán này sẽ được chọn là đỉnh do đỉnh vẫn tồn tại trong đồ thị ban đầu.
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = LLONG_MAX;
struct edge
{
int u, v, w;
};
// Xác định chu trình âm trên đồ thị.
bool check_negative_cycle(vector < edge > &edges, vector < int > &d)
{
for (int i = 1; i < edges.size(); ++i)
{
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
if (d[u] != inf && d[u] + w < d[v])
return true;
}
return false;
}
// Thuật toán Ford Bellman xuất phát từ 1 đỉnh.
void solution(int n, int source, vector < edge > &edges)
{
vector < int > d(n + 1, inf);
d[source] = 0;
// Lặp tối đa n - 1 lần.
for (int step = 1; step <= n - 1; ++step)
{
bool stop = true;
for (int i = 1; i < edges.size(); ++i)
{
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
if (d[u] != inf && d[u] + w < d[v])
{
d[v] = d[u] + w;
stop = false;
}
}
// Nếu không thể tối ưu d[v] nào nữa thì dừng thuật toán.
if (stop) break;
}
if (check_negative_cycle(edges, d))
cout << "successful conspiracy\n";
else
cout << "lamentable kingdom\n";
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
while (true)
{
int n, m;
cin >> n;
if (n == 0)
break;
cin >> m;
vector < edge > edges(m + 1);
for (int i = 1; i <= m; ++i)
{
int si, ni, ki;
string oi;
cin >> si >> ni >> oi >> ki;
int u, v, w;
// Trường hợp s(x) - s(y) > k <=> s(y) - s(x) <= -k - 1.
if (oi == "gt")
{
u = si + ni;
v = si - 1;
w = -ki - 1;
}
else // Trường hợp s(x) - s(y) < k <=> s(x) - s(y) <= k - 1.
{
u = si - 1;
v = si + ni;
w = ki - 1;
}
edges[i] = {u, v, w};
}
for (int u = 1; u <= n; ++u)
edges.push_back({n + 1, u, 0});
// Thực hiện Ford Bellman trên đồ thị gồm n + 2 đỉnh, đỉnh đặc biệt là n + 1.
// Ford Bellman sẽ xuất phát từ đỉnh đặc biệt để đi tìm chu trình âm.
solution(n + 2, n + 1, edges);
}
return 0;
}
2. Giao thông
Đề bài
Một mạng lưới giao thông bao gồm nút giao thông được đánh số từ tới và đoạn đường nối hai chiều giữa một số cặp nút. Trên mỗi đoạn đường, các xe đi qua chỉ được phép giới hạn trọng tải trong khoảng nhất định. Anh Long điều khiển một chiếc xe tải chở hàng từ nút giao thông tới nút giao thông biết rằng nếu chở được càng nhiều hàng thì anh sẽ càng thu về nhiều lợi nhuận.
Yêu cầu: Hãy giúp anh Long tìm một hành trình đi từ nút tới nút sao cho tải trọng xe cho phép trên hành trình đó là lớn nhất? Biết rằng, tải trọng xe cho phép trên hành trình là tải trọng xe cho phép nhỏ nhất trên một đoạn đường của hành trình đó.
Input:
- Dòng đầu tiên chứa hai số nguyên dương .
- Trên dòng tiếp theo, mỗi dòng gồm ba số nguyên dương cho biết có con đường hai chiều với giới hạn tải trọng là nối giữa hai vùng và .
Ràng buộc:
- .
- .
- .
Output:
- Dòng thứ nhất ghi một số nguyên là tải trọng lớn nhất trên hành trình tìm được.
- Dòng thứ hai ghi ra các nút giao thông trên hành trình tìm được, các số phân tách nhau
Sample Input:
6 9
1 2 5
1 4 3
2 4 2
2 3 6
4 5 4
3 4 5
3 5 1
3 6 3
5 6 5
Sample Output:
4
1 2 3 4 5 6
Ý tưởng
Bài toán có thể đưa về đồ thị với các đỉnh là các nút giao thông, còn các cạnh là các con đường.
Giả sử trên một hành trình bất kì tìm được, thì tải trọng xe cho phép trên hành trình này là . Theo đề bài, chính là trọng số của cạnh nhỏ nhất trên hành trình tìm được.
Ta nhận thấy rằng, nếu tìm được một hành trình đi từ tới với tải trọng xe cho phép là thì cũng có thể tìm được một hành trình đi từ tới với tải trọng xe cho phép là . Vì thế, ta có thể thực hiện tìm kiếm nhị phân trên tập kết quả để tìm ra giá trị lớn nhất.
Với một giá trị ta cần xác định có tồn tại đường đi từ tới mà trọng số của tất cả các cạnh đều phải lớn hơn hoặc bằng . Do trọng số các cạnh trên đồ thị không âm, nên ta có thể sử dụng Dijkstra để xác định điều này (trong quá trình Dijkstra chỉ sử dụng các cạnh có trọng số lớn hơn hoặc bằng ).
Do nên ta sẽ sử dụng Dijkstra Heap kết hợp với danh sách kề để biểu diễn đồ thị.
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair < int, int > pi;
const int maxn = 1e5 + 1, inf = 1e18;
vector < pair < int, int > > adj[maxn];
// Truy vết đường đi.
void print_result(int s, int t, int res, vector < int > &last_trace)
{
cout << res << '\n';
vector < int > path;
while (t != s)
{
path.push_back(t);
t = last_trace[t];
}
path.push_back(s);
reverse(path.begin(), path.end());
for (int u: path)
cout << u << ' ';
}
bool check(int n, int limit, vector < int > &last_trace)
{
vector < int > trace(n + 1), d(n + 1, inf);
vector < bool > is_free(n + 1, true);
priority_queue < pi, vector < pi >, less < pi > > qu_min;
d[1] = 0;
qu_min.push({d[1], 1});
while (!qu_min.empty())
{
int u = qu_min.top().second;
int du = qu_min.top().first;
qu_min.pop();
if (u == n)
{
last_trace = trace;
return true;
}
is_free[u] = false;
for (auto e: adj[u])
{
int v = e.first, w = e.second;
if (is_free[v] && w >= limit && d[v] > du + w)
{
d[v] = du + w;
trace[v] = u;
qu_min.push({d[v], v});
}
}
}
return false;
}
void solution(int n)
{
int l = 0, r = 100000, res = 0;
vector < int > last_trace(n + 1);
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(n, mid, last_trace))
{
res = mid;
l = mid + 1;
}
else
r = mid - 1;
}
print_result(1, n, res, last_trace);
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
solution(n);
return 0;
}
V. Tài liệu tham khảo
- https://cp-algorithms.com/graph/bellman_ford.html#shortest-path-faster-algorithm-spfa
- https://cp-algorithms.com/graph/dijkstra.html
- https://cp-algorithms.com/graph/dijkstra_sparse.html
- Tài liệu giáo khoa chuyên Tin quyển 2 - thầy Hồ Sĩ Đàm.
- Giải thuật và Lập trình - thầy Lê Minh Hoàng.
All Rights Reserved