DP trên đồ thị áp dụng quy hoạch động lên các cấu trúc đồ thị. Điểm mấu chốt là xác định thứ tự tính đúng — thường dựa trên thứ tự topo hoặc cấu trúc SCC.
Phân loại
| Loại đồ thị | Kỹ thuật |
|---|---|
| DAG (đồ thị có hướng không chu trình) | DP theo thứ tự topo |
| Đồ thị có chu trình | Rút gọn SCC → DAG, rồi DP |
| Đồ thị vô hướng / cây | DP trên cây (xem trang riêng) |
Dạng 1: DP trên DAG
Vì DAG không có chu trình, tồn tại thứ tự topo — đảm bảo khi tính dp[v] thì mọi dp[u] với cạnh đã được tính xong.
Đường đi dài nhất trên DAG
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int,int>> adj[100005]; // {v, weight}
vector<int> order; // thứ tự topo
bool visited[100005];
long long dp[100005];
void dfs(int u) {
visited[u] = true;
for (auto [v, w] : adj[u])
if (!visited[v]) dfs(v);
order.push_back(u);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
}
for (int i = 1; i <= n; i++)
if (!visited[i]) dfs(i);
reverse(order.begin(), order.end()); // topo order
fill(dp + 1, dp + n + 1, LLONG_MIN);
dp[1] = 0; // xuất phát từ nút 1
for (int u : order) {
if (dp[u] == LLONG_MIN) continue;
for (auto [v, w] : adj[u])
dp[v] = max(dp[v], dp[u] + w);
}
cout << *max_element(dp + 1, dp + n + 1) << "\n";
}
Đếm số đường đi trên DAG
// cnt[v] = số đường đi từ nguồn đến v
vector<long long> cnt(n + 1, 0);
cnt[src] = 1;
for (int u : topo_order) {
for (auto [v, w] : adj[u])
cnt[v] = (cnt[v] + cnt[u]) % MOD;
}
Dạng 2: DP trên đồ thị có chu trình — SCC + DAG
Nếu đồ thị có chu trình, DP thông thường không áp dụng được. Giải pháp:
- Tìm tất cả SCC (Strongly Connected Components) — dùng Tarjan hoặc Kosaraju.
- Rút gọn đồ thị thành DAG của các SCC.
- DP trên DAG vừa tạo.
// Sau khi tìm SCC, mỗi SCC được gán một ID
// Xây DAG mới: cạnh giữa các SCC
// dp[scc_id] = giá trị tối ưu cho SCC đó
// Ví dụ: tìm đường đi dài nhất (theo số nút) trên đồ thị có chu trình
// - Trong một SCC có k nút: có thể đi k nút liên tiếp (cycle)
// - Giữa các SCC: dp theo topo của DAG rút gọn
Cài đặt Kosaraju tìm SCC
vector<int> adj[MAXN], radj[MAXN];
bool vis[MAXN];
vector<int> order2, comp;
int scc_id[MAXN];
void dfs1(int u) {
vis[u] = true;
for (int v : adj[u]) if (!vis[v]) dfs1(v);
order2.push_back(u);
}
void dfs2(int u, int id) {
scc_id[u] = id;
for (int v : radj[u]) if (scc_id[v] == -1) dfs2(v, id);
}
int kosaraju(int n) {
for (int i = 1; i <= n; i++) if (!vis[i]) dfs1(i);
memset(scc_id, -1, sizeof(scc_id));
int num_scc = 0;
for (int i = n - 1; i >= 0; i--) {
int u = order2[i];
if (scc_id[u] == -1) dfs2(u, num_scc++);
}
return num_scc;
}
Dạng 3: DP với Dijkstra (Shortest Path DP)
Khi bài toán kết hợp đường đi ngắn nhất và DP, có thể nhúng trạng thái DP vào hàng đợi ưu tiên của Dijkstra.
Bài toán: Tìm đường đi ngắn nhất từ đến với tối đa cạnh được phép đổi màu (chi phí cạnh đổi màu giảm về 0).
// Trạng thái: (u, changes_used)
// dp[u][j] = khoảng cách ngắn nhất đến u đã dùng j lần đổi màu
vector<vector<long long>> dist(n + 1, vector<long long>(k + 1, LLONG_MAX));
priority_queue<tuple<long long,int,int>, vector<tuple<long long,int,int>>, greater<>> pq;
dist[s][0] = 0;
pq.push({0, s, 0});
while (!pq.empty()) {
auto [d, u, changes] = pq.top(); pq.pop();
if (d > dist[u][changes]) continue;
for (auto [v, w, color] : adj[u]) {
// Không đổi màu
if (dist[u][changes] + w < dist[v][changes]) {
dist[v][changes] = dist[u][changes] + w;
pq.push({dist[v][changes], v, changes});
}
// Đổi màu (w = 0)
if (changes < k && dist[u][changes] < dist[v][changes + 1]) {
dist[v][changes + 1] = dist[u][changes];
pq.push({dist[v][changes + 1], v, changes + 1});
}
}
}
long long ans = *min_element(dist[t].begin(), dist[t].end());
Dạng 4: DP trên DAG ngầm (Implicit DAG)
Đôi khi DAG không được cho tường minh mà được xác định bởi điều kiện. Ví dụ:
Bài toán: Cho công việc, công việc phải hoàn thành trước công việc nếu và . Tìm chuỗi công việc dài nhất có thể thực hiện.
// Đây chính là LIS 2D (Longest Increasing Subsequence trên 2 chiều)
// Sắp xếp theo a[i], rồi DP theo b[i]
sort(jobs.begin(), jobs.end()); // sắp theo a
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
for (int j = 0; j < i; j++)
if (jobs[j].a < jobs[i].a && jobs[j].b < jobs[i].b)
dp[i] = max(dp[i], dp[j] + 1);
Dạng 5: DP đếm đường đi với ràng buộc trạng thái
Bài toán: Cho đồ thị nút, đếm số đường đi đơn (không lặp nút) từ đến có đúng cạnh.
Với nhỏ: dùng DP bitmask — dp[mask][u] = số đường đi qua đúng tập nút mask, kết thúc tại u.
// dp[mask][u] = số đường đi dùng đúng tập nút mask, kết thúc tại u
vector<vector<long long>> dp(1 << n, vector<long long>(n, 0));
dp[1 << s][s] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (!dp[mask][u]) continue;
if (!((mask >> u) & 1)) continue;
for (int v = 0; v < n; v++) {
if ((mask >> v) & 1) continue; // v đã thăm
if (!edge[u][v]) continue;
dp[mask | (1 << v)][v] += dp[mask][u];
}
}
}
cout << dp[(1<<n)-1][t]; // đường Hamilton nếu mask đầy
Tổng kết
| Bài toán | Kỹ thuật |
|---|---|
| Đường đi dài/ngắn nhất trên DAG | Topo sort + DP |
| Đếm đường đi trên DAG | Topo sort + DP đếm |
| DP trên đồ thị có chu trình | SCC → DAG rút gọn → DP |
| Shortest path + DP trạng thái | Dijkstra với trạng thái mở rộng |
| Đường đi đơn, nhỏ | DP bitmask trên đồ thị |
| Đường đi dài bước, đồ thị nhỏ | Matrix Exponentiation |
Bình luận