Chở lúa qua cầu (Đề tự luyện HSG Tin 9 – Bài 3)
Đề bài
Chở lúa qua cầu. Có $N$ xã và $M$ con đường hai chiều, đường $i$ nối $u_i, v_i$ qua cây cầu tải trọng $c_i$ tấn. Xe chở $W$ tấn chỉ qua được cầu có tải trọng $\ge W$. Tìm $W$ lớn nhất sao cho có đường đi từ xã $1$ tới xã $N$, và với $W$ đó, số cây cầu ít nhất phải đi qua. Dữ liệu đảm bảo xã $1$ đi được tới xã $N$.
Dữ liệu vào: dòng 1 là $N, M$ $(2 \le N \le 10^5,\ 1 \le M \le 2\cdot10^5)$; $M$ dòng sau là $u_i, v_i, c_i$ $(u_i \ne v_i,\ 1 \le c_i \le 10^9)$.
Kết quả: hai số $W$ và $S$.
- Subtask 1 (20%): mọi cây cầu cùng tải trọng.
- Subtask 2 (30%): $N \le 2000$, $M \le 4000$.
- Subtask 3 (50%): không ràng buộc thêm.
6 9
3 5 16
6 5 11
3 2 17
3 1 10
4 3 6
5 4 10
1 4 13
2 1 8
5 2 110 3Chở được $10$ tấn, ví dụ theo đường $1 \to 3 \to 5 \to 6$ (cầu $10, 16, 11$). Không cách nào chở được $11$ tấn, và với $10$ tấn không cách nào qua ít hơn $3$ cây cầu.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Chở lúa qua cầuLời mở đầu
Bài có hai mục tiêu xếp theo thứ tự ưu tiên: trước hết là chở nặng nhất, sau đó mới tới đi ít cầu nhất. Đừng vội "gộp" hai mục tiêu: con đường ít cầu nhất trên bản đồ có thể đi qua một cây cầu rất yếu, còn con đường "chắc" nhất thì có thể vòng vèo rất xa.
Nhận xét quan trọng nhất: nếu xe chở được $W$ tấn thì cũng chở được mọi khối lượng nhẹ hơn (cầu nào chịu được $W$ thì chịu được khối lượng nhỏ hơn). Ngược lại, nếu không chở được $W$ tấn thì nặng hơn càng không được. Hãy tưởng tượng ta "xóa" khỏi bản đồ mọi cây cầu yếu hơn $W$: khi $W$ tăng dần, các cây cầu biến mất dần, tới một lúc xã $1$ bị cắt đứt khỏi xã $N$.
Hình 1. "Chở được hay không" đổi từ được sang không đúng một lần khi $W$ tăng. Đáp án $W$ là điểm cuối cùng còn "được" — tìm điểm ranh giới như vậy chính là việc của chặt nhị phân.
Thêm một nhận xét nữa: $W$ tối ưu luôn là tải trọng của một cây cầu nào đó (đó là cây cầu yếu nhất trên con đường tốt nhất). Vậy chỉ cần xét các giá trị $c_i$, không phải mọi số từ $1$ tới $10^9$.
Còn mục tiêu thứ hai thì dễ: khi đã biết $W$, chỉ giữ các cầu có tải trọng $\ge W$ và chạy BFS từ xã $1$ — BFS trên đồ thị không trọng số cho đúng số cạnh ít nhất.
Cách 1Mọi cầu cùng tải trọng: BFS thường – O(N + M) · 20%
Khi mọi cây cầu cùng tải trọng $c$, xe chở được đúng $c$ tấn và đi được mọi con đường. Đáp án là $W = c$ và $S$ = số cạnh ít nhất từ $1$ tới $N$, tìm bằng BFS: xuất phát từ xã $1$ với $d[1] = 0$, mỗi lần lấy một xã $u$ khỏi hàng đợi thì mọi xã kề $v$ chưa thăm nhận $d[v] = d[u] + 1$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> ke(n + 1);
int W = 0;
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
ke[u].push_back(v);
ke[v].push_back(u);
W = c; // moi cau cung tai trong -> cho duoc dung W tan
}
// BFS tim so cau it nhat tu xa 1 toi xa n
vector<int> d(n + 1, -1);
queue<int> q;
d[1] = 0; q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : ke[u])
if (d[v] == -1) { d[v] = d[u] + 1; q.push(v); }
}
cout << W << ' ' << d[n] << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
ke = [[] for _ in range(n + 1)]
W = 0
for i in range(m):
u = int(data[2 + 3 * i]); v = int(data[3 + 3 * i])
W = int(data[4 + 3 * i]) # moi cau cung tai trong -> cho duoc dung W tan
ke[u].append(v)
ke[v].append(u)
# BFS tim so cau it nhat tu xa 1 toi xa n
d = [-1] * (n + 1)
d[1] = 0
q = [1]
for u in q:
for v in ke[u]:
if d[v] == -1:
d[v] = d[u] + 1
q.append(v)
print(W, d[n])
main()Cách 2Thử từng mức tải trọng – O(M · (N + M)) · 50%
Lấy các giá trị tải trọng khác nhau, xếp giảm dần, rồi thử lần lượt: với mỗi mức $W$, chạy BFS chỉ qua các cầu có $c \ge W$. Mức đầu tiên mà BFS tới được xã $N$ chính là $W$ lớn nhất, và khoảng cách BFS lúc đó chính là $S$.
| Thử W | Các cầu còn giữ (c ≥ W) | Tới được xã 6? |
|---|---|---|
| 17 | 3–2 | không |
| 16 | 3–2, 3–5 | không |
| 13 | 3–2, 3–5, 1–4 | không |
| 11 | thêm 6–5 | không (từ xã 1 chỉ sang được xã 4) |
| 10 | thêm 3–1, 5–4 | được, BFS cho $d[6] = 3$ |
Chạy tay ví dụ: dừng ở $W = 10$, đáp án $10\ 3$. Mỗi lần BFS tốn $O(N + M)$ và có thể phải thử tới $M$ mức: với $N = 2000, M = 4000$ là khoảng $2{,}4\cdot10^7$ — ổn. Nhưng với $M = 2\cdot10^5$ mức thì chịu.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<pair<int, int>>> ke; // ke[u] = {(v, tai trong cau)}
// BFS chi di qua cac cau co tai trong >= W; tra ve so cau it nhat toi xa n (-1 neu khong toi)
int bfs(int W) {
vector<int> d(n + 1, -1);
queue<int> q;
d[1] = 0; q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto [v, c] : ke[u])
if (c >= W && d[v] == -1) { d[v] = d[u] + 1; q.push(v); }
}
return d[n];
}
int main() {
cin >> n >> m;
ke.assign(n + 1, {});
vector<int> cs(m);
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
ke[u].push_back({v, c});
ke[v].push_back({u, c});
cs[i] = c;
}
sort(cs.rbegin(), cs.rend()); // tu nang toi nhe
cs.erase(unique(cs.begin(), cs.end()), cs.end());
for (int W : cs) { // thu tung muc tai trong
int s = bfs(W);
if (s != -1) { // muc dau tien toi duoc = lon nhat
cout << W << ' ' << s << '\n';
return 0;
}
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
ke = [[] for _ in range(n + 1)]
cs = []
for i in range(m):
u = int(data[2 + 3 * i]); v = int(data[3 + 3 * i]); c = int(data[4 + 3 * i])
ke[u].append((v, c))
ke[v].append((u, c))
cs.append(c)
for W in sorted(set(cs), reverse=True): # thu tung muc tai trong, tu nang toi nhe
d = [-1] * (n + 1)
d[1] = 0
q = [1]
for u in q: # BFS chi qua cau tai trong >= W
for v, c in ke[u]:
if c >= W and d[v] == -1:
d[v] = d[u] + 1
q.append(v)
if d[n] != -1: # muc dau tien toi duoc = lon nhat
print(W, d[n])
return
main()Cách 3Chặt nhị phân trên các mức tải trọng + BFS – O((N + M) log M) · 100%
Thay vì thử lần lượt, ta dùng tính chất "được – được – … – được – không – … – không" ở Hình 1. Xếp các mức tải trọng khác nhau tăng dần thành mảng $cs[0..K-1]$. Mức $cs[0]$ (cầu yếu nhất) chắc chắn chở được vì khi đó mọi cầu đều dùng được và đề đảm bảo có đường. Ta tìm chỉ số $lo$ lớn nhất mà $cs[lo]$ còn chở được:
- Giữ $lo$ là chỉ số chắc chắn được, $hi$ là chỉ số lớn nhất có thể được; ban đầu $lo = 0$, $hi = K - 1$.
- Lấy $mid = \lfloor (lo + hi + 1)/2 \rfloor$ (làm tròn lên, nếu không vòng lặp có thể kẹt mãi khi $hi = lo + 1$). Chạy BFS với $W = cs[mid]$: nếu tới được xã $N$ thì $lo = mid$, ngược lại $hi = mid - 1$.
- Khi $lo = hi$: $W = cs[lo]$; chạy BFS thêm một lần để lấy $S$.
Ví dụ: $cs = [1, 6, 8, 10, 11, 13, 16, 17]$. Lần 1: $mid = 4$ ($W = 11$) không tới được, $hi = 3$. Lần 2: $mid = 2$ ($W = 8$) tới được, $lo = 2$. Lần 3: $mid = 3$ ($W = 10$) tới được, $lo = 3$. Dừng: $W = 10$, BFS cho $S = 3$. Chỉ cần khoảng $\log_2 M \approx 18$ lần BFS thay vì $M$ lần.
hi = 1000000000 rồi coi $hi$ là giá trị "không chở được". Khi đáp án đúng bằng $10^9$ thì code này ra $999999999$. Bộ test có 4 test như vậy. Chặt trên mảng các mức tải trọng như dưới đây thì không lo chuyện này, lại chỉ cần khoảng 18 lần BFS thay vì 30.Mô phỏng dưới đây chạy chặt nhị phân trên đồ thị em nhập (mỗi con đường ghi "u v c", cách nhau dấu chấm phẩy) và tô các xã BFS thăm được ở mỗi lần thử.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<pair<int, int>>> ke; // ke[u] = {(v, tai trong cau)}
vector<int> d;
// BFS chi di qua cac cau co tai trong >= W; tra ve so cau it nhat tu xa 1 toi xa n (-1 neu khong toi duoc)
int bfs(int W) {
d.assign(n + 1, -1);
queue<int> q;
d[1] = 0; q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto [v, c] : ke[u])
if (c >= W && d[v] == -1) {
d[v] = d[u] + 1;
if (v == n) return d[v]; // toi xa n roi: BFS cho so cau it nhat
q.push(v);
}
}
return d[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
ke.assign(n + 1, {});
vector<int> cs(m);
for (int i = 0; i < m; i++) {
int u, v, c;
cin >> u >> v >> c;
ke[u].push_back({v, c});
ke[v].push_back({u, c});
cs[i] = c;
}
sort(cs.begin(), cs.end());
cs.erase(unique(cs.begin(), cs.end()), cs.end()); // cac muc tai trong khac nhau
// chat nhi phan: tim muc lon nhat ma van toi duoc xa n
int lo = 0, hi = cs.size() - 1; // cs[0] chac chan toi duoc (de bai dam bao)
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (bfs(cs[mid]) != -1) lo = mid; // cho duoc cs[mid] tan -> thu nang hon
else hi = mid - 1;
}
cout << cs[lo] << ' ' << bfs(cs[lo]) << '\n';
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1])
U = data[2:3 * m + 2:3]; V = data[3:3 * m + 3:3]; C = data[4:3 * m + 4:3]
us = [int(x) for x in U]; vs = [int(x) for x in V]; cs = [int(x) for x in C]
# danh sach ke dang mang phang (CSR), moi xa xep cau theo tai trong GIAM dan:
# khi gap cau < W thi cac cau con lai cung < W, dung luon
order = sorted(range(m), key=cs.__getitem__, reverse=True)
deg = [0] * (n + 2)
for i in range(m):
deg[us[i]] += 1; deg[vs[i]] += 1
start = [0] * (n + 2)
for u in range(1, n + 1):
start[u + 1] = start[u] + deg[u]
pos = start[:]
to = [0] * (2 * m); cap = [0] * (2 * m)
for i in order:
u, v, c = us[i], vs[i], cs[i]
to[pos[u]] = v; cap[pos[u]] = c; pos[u] += 1
to[pos[v]] = u; cap[pos[v]] = c; pos[v] += 1
def bfs(W):
# BFS chi qua cau tai trong >= W; so cau it nhat toi xa n (-1 neu khong toi)
d = [-1] * (n + 1)
d[1] = 0
q = [1]
for u in q:
du = d[u] + 1
for k in range(start[u], start[u + 1]):
if cap[k] < W:
break
v = to[k]
if d[v] < 0:
d[v] = du
if v == n:
return du
q.append(v)
return d[n]
lv = sorted(set(cs)) # cac muc tai trong khac nhau
lo, hi = 0, len(lv) - 1
while lo < hi: # chat nhi phan muc lon nhat van toi duoc
mid = (lo + hi + 1) // 2
if bfs(lv[mid]) != -1:
lo = mid
else:
hi = mid - 1
print(lv[lo], bfs(lv[lo]))
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 32 test: Subtask 1 có 10 test (mọi cầu cùng tải trọng, gồm $N = 2$, tải trọng $1$ và $10^9$, đồ thị "dài" có $S$ tới $37941$), Subtask 2 có 10 test ($N \approx 2000$, $M \approx 4000$, gồm ví dụ), Subtask 3 có 12 test ($N$ tới $10^5$, $M$ tới $2\cdot10^5$). Các kiểu đồ thị: ngẫu nhiên với lối tắt "ít cầu nhưng yếu" từ xã 1 tới xã $N$; một con đường rất dài chắc chắn cùng nhiều lối tắt yếu; hai con đường cùng "độ chắc" nhưng dài ngắn khác nhau; một cụm xã nối bằng cầu rất chắc với xã 1 nhưng không dẫn tới xã $N$ (làm Cách 2 phải BFS rất nhiều lần); nhiều cầu song song; đáp án đúng bằng $10^9$. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (10 test) | Sub 3 (12 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – BFS thường, $W$ = tải trọng chung | Đúng 10/10 | WA 0/10 | WA 0/12 | 20 |
| Cách 2 – Thử từng mức tải trọng | Đúng 10/10 | Đúng 10/10 | TLE 0/12 | 50 |
| Cách 3 – Chặt nhị phân + BFS (chuẩn) | Đúng 10/10 | Đúng 10/10 | Đúng 12/12 | 100 |
| Sai: BFS bỏ qua tải trọng rồi lấy cầu yếu nhất trên đường đó | Đúng 10/10 | WA 1/10 | WA 0/12 | 23 |
| Sai: $W$ đúng nhưng đếm số cầu trên cả bản đồ | Đúng 10/10 | WA 1/10 | WA 2/12 | 31,3 |
| Sai: cây khung lớn nhất (Kruskal), $S$ lấy theo đường trên cây | WA 3/10 | WA 6/10 | WA 7/12 | 53,2 |
| Sai: chặt nhị phân trên $[1, 10^9)$, bỏ sót $W = 10^9$ | WA 7/10 | WA 9/10 | Đúng 12/12 | 91 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test Subtask 1 và sai ở toàn bộ 22 test còn lại; Cách 2 đúng 20/20 test của hai subtask đầu và quá thời gian (hơn 3 giây; vài test mình đo thử còn chạy hơn 30 giây) ở cả 12 test Subtask 3; Cách 3 đúng 32/32 test. Lời giải Python của Cách 3 cũng đúng 32/32 test (nên nộp bằng PyPy 3). Lời giải dùng cây khung lớn nhất là một ý rất hay để tìm $W$ — nó luôn tìm đúng $W$ — nhưng đường đi trên cây khung không phải đường ít cầu nhất, nên mất gần một nửa số điểm. Ví dụ của đề được chọn sao cho cả bốn lời giải sai trong bảng đều ra đúng 10 3.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét