Bài toán cứu hộ trên đảo hoang (P4011)
Bài toán yêu cầu tìm bước đi ngắn nhất từ ô (1,1) đến ô (n,m) trong một mê cung kích thước $n \times m$. Mê cung này không chỉ có các bức tường ngăn cách mà còn có các cánh cửa khóa và chìa khóa tương ứng. Để đi qua một cánh cửa, người chơi phải sở hữu loại chìa khóa phù hợp.
Phân tích thuật toán
Với yêu cầu tìm đường đi ngắn nhất trong mê cung, thuật toán BFS (Breadth-First Search) là lựa chọn hàng đầu. Tuy nhiên, BFS thông thường chỉ lưu trữ vị trí $(x, y)$, điều này không đủ để xử lý trường hợp trạng thái thay đổi khi nhặt được chìa khóa. Nếu chỉ dùng mảng đánh dấu visited[x][y], chúng ta có thể bỏ lỡ việc quay lại một vị trí cũ sau khi đã có thêm chìa khóa mới để mở một cánh cửa khác.
Do giới hạn $n, m, p \le 10$, ta có thể sử dụng kỹ thuật nén trạng thái (Bitmask). Trạng thái của BFS sẽ là một bộ ba $(x, y, state)$, trong đó state là một số nguyên biểu diễn tập hợp các chìa khóa hiện có dưới dạng nhị phân. Nếu có chìa khóa loại $i$, bit thứ $i$ trong state sẽ được bật.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct State {
int r, c, keys, dist;
};
int N, M, P, K;
int wall_door[11][11][11][11];
int keys_at[11][11];
bool visited[11][11][1 << 11];
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};
int solve() {
queue<State> q;
int start_keys = keys_at[1][1];
q.push({1, 1, start_keys, 0});
visited[1][1][start_keys] = true;
while (!q.empty()) {
State curr = q.front();
q.pop();
if (curr.r == N && curr.c == M) return curr.dist;
for (int i = 0; i < 4; ++i) {
int nr = curr.r + dr[i];
int nc = curr.c + dc[i];
if (nr < 1 || nr > N || nc < 1 || nc > M) continue;
int gate = wall_door[curr.r][curr.c][nr][nc];
if (gate == -1) continue; // Wall
if (gate > 0 && !(curr.keys & (1 << gate))) continue; // Locked
int n_keys = curr.keys | keys_at[nr][nc];
if (!visited[nr][nc][n_keys]) {
visited[nr][nc][n_keys] = true;
q.push({nr, nc, n_keys, curr.dist + 1});
}
}
}
return -1;
}
Bài toán ghép cặp phi công (P2756)
Đây là một bài toán kinh điển về tìm ghép cặp cực đại trên đồ thị hai phía (Bipartite Matching). Chúng ta có hai nhóm: phi công nước ngoài và phi công trong nước. Mỗi cặp phi công phối hợp được với nhau sẽ tạo thành một cạnh nối giữa hai tập hợp.
Giải pháp
Có hai cách tiếp cận phổ biến:
- Sử dụng thuật toán Hungary để tìm đường tăng cường.
- Sử dụng luồng cực đại (Dinic hoặc Edmonds-Karp) bằng cách thêm điểm phát (Source) nối tới nhóm 1 và điểm thu (Sink) nối từ nhóm 2, tất cả các cạnh có dung lượng bằng 1.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int M, N;
vector<int> adj[105];
int match_partner[105];
bool check[105];
bool dfs_find(int u) {
for (int v : adj[u]) {
if (!check[v]) {
check[v] = true;
if (match_partner[v] == -1 || dfs_find(match_partner[v])) {
match_partner[v] = u;
return true;
}
}
}
return false;
}
void process() {
memset(match_partner, -1, sizeof(match_partner));
int total_pairs = 0;
for (int i = 1; i <= M; ++i) {
memset(check, false, sizeof(check));
if (dfs_find(i)) total_pairs++;
}
cout << total_pairs << endl;
for (int i = M + 1; i <= N; ++i) {
if (match_partner[i] != -1) {
cout << match_partner[i] << " " << i << endl;
}
}
}
Bài toán bản vá phần mềm (P2761)
Mỗi phần mềm có $n$ lỗi và có $m$ bản vá. Một bản vá chỉ có thể áp dụng nếu hệ thống thỏa mãn điều kiện nhất định (có một số lỗi và không có một số lỗi khác). Sau khi dùng bản vá, một số lỗi biến mất nhưng một số lỗi mới có thể xuất hiện.
Mô hình hóa đồ thị
Chúng ta coi mỗi trạng thái của lỗi là một đỉnh trong đồ thị. Vì tối đa có 20 lỗi, tổng số trạng thái là $2^{20}$. Bài toán tìm thời gian ngắn nhất để sạch lỗi trở thành bài toán tìm đường đi ngắn nhất từ trạng thái "tất cả lỗi" (bitmask toàn 1) đến trạng thái "không lỗi" (0). Thuật toán Dijkstra hoặc SPFA là phù hợp để giải quyết vấn đề này.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
int duration[105];
int b1[105], b2[105], f1[105], f2[105];
int dist[1 << 20];
void spfa() {
memset(dist, 0x3f, sizeof(dist));
int start = (1 << n) - 1;
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (int i = 0; i < m; ++i) {
if ((u & b1[i]) == b1[i] && (u & b2[i]) == 0) {
int v = (u & ~f1[i]) | f2[i];
if (dist[v] > dist[u] + duration[i]) {
dist[v] = dist[u] + duration[i];
pq.push({dist[v], v});
}
}
}
}
}
Bài toán cân bằng tải kho hàng (P4016)
Có $n$ kho hàng sắp xếp theo vòng tròn, mỗi kho có lượng hàng khác nhau. Mục tiêu là chuyển hàng giữa các kho kề nhau sao cho lượng hàng tại mỗi kho bằng nhau với chi phí vận chuyển thấp nhất.
Phương pháp Luồng chi phí cực tiểu (MCMF)
Xây dựng mạng luồng như sau:
- Tính lượng hàng trung bình $avg$.
- Nếu kho $i$ có $A_i > avg$, nối từ Source đến $i$ với dung lượng $A_i - avg$ và chi phí 0.
- Nếu kho $i$ có $A_i < avg$, nối từ $i$ đến Sink với dung lượng $avg - A_i$ và chi phí 0.
- Nối giữa các kho kề nhau $(i, j)$ với dung lượng vô hạn và chi phí 1 (vận chuyển 2 chiều).
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 105;
const int INF = 1e9;
struct Edge {
int to, cap, flow, cost, rev;
};
vector<Edge> g[MAXN + 2];
int dist[MAXN + 2], parent_e[MAXN + 2], parent_v[MAXN + 2];
void add_edge(int u, int v, int cap, int cost) {
g[u].push_back({v, cap, 0, cost, (int)g[v].size()});
g[v].push_back({u, 0, 0, -cost, (int)g[u].size() - 1});
}
int solve_mcmf(int s, int t) {
int min_cost = 0;
while (true) {
fill(dist, dist + MAXN + 2, INF);
dist[s] = 0;
queue<int> q;
vector<bool> in_queue(MAXN + 2, false);
q.push(s);
in_queue[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
in_queue[u] = false;
for (int i = 0; i < g[u].size(); ++i) {
Edge &e = g[u][i];
if (e.cap > e.flow && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
parent_v[e.to] = u;
parent_e[e.to] = i;
if (!in_queue[e.to]) {
q.push(e.to);
in_queue[e.to] = true;
}
}
}
}
if (dist[t] == INF) break;
int push = INF;
for (int v = t; v != s; v = parent_v[v]) {
Edge &e = g[parent_v[v]][parent_e[v]];
push = min(push, e.cap - e.flow);
}
for (int v = t; v != s; v = parent_v[v]) {
Edge &e = g[parent_v[v]][parent_e[v]];
e.flow += push;
g[v][e.rev].flow -= push;
min_cost += push * e.cost;
}
}
return min_cost;
}