Thửa ruộng (Đề tự luyện HSG Tin quốc gia – Bài 4) – Mô hình hoá thành lát cắt hẹp nhất: mỗi thửa một “chuỗi mức nước”, cạnh lệch tầng cho ngưỡng chênh lệch, luồng cực đại Dinic
Đề bài
Thửa ruộng. Cánh đồng thầy Sơn chăm có $N$ thửa ruộng. Thầy chọn cho mỗi thửa $i$ một mực nước nguyên $h_i \in [0, H]$; giữ thửa $i$ ở mức $h$ tốn $c_{i,h}$ đồng. Có $M$ con bờ, bờ $k$ ngăn hai thửa $u_k, v_k$, có độ cao an toàn $d_k$ và hệ số gia cố $w_k$: bờ tốn $w_k \cdot \max(0,\ |h_{u_k} - h_{v_k}| - d_k)$ đồng (chênh lệch không quá $d_k$ thì không tốn gì, mỗi phân vượt quá tốn $w_k$). Hãy chọn các $h_i$ để tổng chi phí (giữ nước + gia cố bờ) nhỏ nhất.
Dữ liệu vào: dòng đầu $N, M, H$ $(N \le 200,\ M \le 1000,\ H \le 30)$; $N$ dòng tiếp, dòng $i$ gồm $c_{i,0}, \ldots, c_{i,H}$ $(0 \le c \le 10^9)$; $M$ dòng cuối, mỗi dòng $u, v, w, d$ $(1 \le w \le 10^9,\ 0 \le d \le H)$, không có hai bờ cùng ngăn một cặp thửa.
Kết quả: tổng chi phí nhỏ nhất.
- Subtask 1 (10%): $N \le 8$ và $H \le 3$.
- Subtask 2 (15%): các bờ tạo thành một cây ($M = N - 1$, liên thông).
- Subtask 3 (20%): $H = 1$.
- Subtask 4 (25%): $d_k = 0$ với mọi $k$.
- Subtask 5 (30%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 5 giây.
Input
5 6 3
5 2 5 4
7 6 0 1
8 0 0 8
0 7 7 5
6 9 3 4
1 4 1 0
2 5 1 2
2 3 2 0
3 5 1 1
1 5 1 2
2 4 2 0Output
10Giải thích
Cách chọn tốt nhất là $h = (1, 2, 2, 0, 2)$. Chi phí giữ nước $2 + 0 + 0 + 0 + 3 = 5$; bờ $1 - 4$ ($d = 0$) chênh $1$ tốn $1$; bờ $2 - 4$ ($d = 0$) chênh $2$ tốn $2 \cdot 2 = 4$; bờ $1 - 5$ ($d = 2$) chênh $1 \le 2$ không tốn; các bờ còn lại hai bên bằng nhau. Tổng $10$.
Dành cho học viênNộp bài trên ClueOJ
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 Thửa ruộngLời mở đầu
Đây là bài cuối của đề, và nó khó vì một lý do rất "đặc biệt": thuật toán cần dùng (luồng cực đại) là thuật toán quen thuộc, nhưng nhìn ra bài toán là một bài lát cắt thì không dễ chút nào. Đề không hề nhắc tới nguồn, đích hay luồng – chỉ có các thửa ruộng, mực nước và những con bờ.
Hãy để ý cấu trúc của hàm chi phí:
$$\text{Chi phí} = \sum_{i} c_{i, h_i} \;+\; \sum_{k} w_k \cdot \max\big(0,\ |h_{u_k} - h_{v_k}| - d_k\big).$$- Phần thứ nhất: mỗi thửa "tự chọn" mức của mình – dễ.
- Phần thứ hai: mỗi bờ "phạt" hai thửa kề nhau nếu mực nước chênh nhau nhiều – đây là phần làm bài toán khó, vì các thửa ràng buộc lẫn nhau theo một đồ thị bất kỳ (có chu trình).
Mấu chốt của lời giải đầy đủ: biến mỗi cách chọn mực nước thành một lát cắt trên một đồ thị được dựng khéo, sao cho giá trị lát cắt đúng bằng tổng chi phí. Khi đó lát cắt hẹp nhất (= luồng cực đại) chính là đáp án. Ý tưởng then chốt là "chuỗi mức nước": mỗi thửa ứng với một chuỗi $H$ đỉnh, và vị trí bị cắt trên chuỗi cho biết mực nước của thửa.
Chuỗi mức nước của một thửa (ví dụ $H = 4$): đỉnh "$\ge j$" nằm phía $s$ nghĩa là "thửa có mực nước ít nhất $j$". Lát cắt cắt chuỗi ở cạnh $c_h$ $\iff$ chọn mực nước $h$.
Mình sẽ đi từ dễ đến khó qua 5 cách, mỗi cách ứng với một subtask:
Cách 1Vét cạn · 10%Cách 2QHĐ trên cây · 25%Cách 3H = 1: lát cắt cơ bản · 45%Cách 4d = 0: chuỗi mức nước · 70%Cách 5Cạnh lệch tầng · 100%
Cách 1Vét cạn – O((H + 1)^N · (N + M)) · 10%
Thử mọi cách chọn $(h_1, \ldots, h_N)$ bằng đệ quy, với mỗi cách tính tổng chi phí trực tiếp theo công thức và lấy nhỏ nhất. Với $N \le 8$, $H \le 3$ có tối đa $4^8 = 65\,536$ cách chọn – rất nhanh.
long long
Chi phí mỗi thửa tới $10^9$, cộng $N$ thửa đã vượt int. Các bờ còn có thể tốn tới $10^9 \cdot 30$ mỗi bờ. Dùng long long cho mọi tổng.#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, H;
vector<vector<ll>> c;
vector<int> U, V, D, h;
vector<ll> W;
ll best = LLONG_MAX;
void tryAll(int i) { // chon muc nuoc cho thua i
if (i == n) {
ll cost = 0;
for (int k = 0; k < n; k++) cost += c[k][h[k]];
for (int e = 0; e < m; e++) cost += W[e] * max(0, abs(h[U[e]] - h[V[e]]) - D[e]);
best = min(best, cost);
return;
}
for (int x = 0; x <= H; x++) { h[i] = x; tryAll(i + 1); }
}
int main() {
scanf("%d %d %d", &n, &m, &H);
c.assign(n, vector<ll>(H + 1));
for (int i = 0; i < n; i++) for (int x = 0; x <= H; x++) scanf("%lld", &c[i][x]);
U.resize(m); V.resize(m); D.resize(m); W.resize(m); h.assign(n, 0);
for (int e = 0; e < m; e++) { scanf("%d %d %lld %d", &U[e], &V[e], &W[e], &D[e]); U[e]--; V[e]--; }
tryAll(0);
printf("%lld\n", best);
return 0;
}import sys
from itertools import product
def main():
data = sys.stdin.buffer.read().split()
n, m, H = int(data[0]), int(data[1]), int(data[2])
p = 3
c = []
for i in range(n):
c.append([int(x) for x in data[p:p + H + 1]]); p += H + 1
edges = []
for _ in range(m):
u, v, w, d = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]), int(data[p + 3]); p += 4
edges.append((u, v, w, d))
best = None
for h in product(range(H + 1), repeat=n): # thu moi cach chon muc nuoc
cost = 0
for i in range(n):
cost += c[i][h[i]]
for u, v, w, d in edges:
diff = abs(h[u] - h[v]) - d
if diff > 0:
cost += w * diff
if best is None or cost < best:
best = cost
print(best)
main()Không gian$O(N + M)$
Thời gian$O((H + 1)^N (N + M))$
Cách 2Các bờ tạo thành cây: QHĐ trên cây – O(N · H²) · 25%
Khi các bờ tạo thành một cây, ta treo cây ở thửa $1$. Gọi $f[v][x]$ là chi phí nhỏ nhất của cây con gốc $v$ (chi phí giữ nước của các thửa trong cây con + chi phí các bờ trong cây con) khi thửa $v$ có mực nước $x$. Các cây con của các con của $v$ chỉ "nói chuyện" với nhau qua $v$, nên:
$$f[v][x] = c_{v,x} + \sum_{\text{con } u \text{ của } v} \ \min_{0 \le y \le H} \Big( f[u][y] + w_{uv} \cdot \max(0, |x - y| - d_{uv}) \Big).$$Đáp án là $\min_x f[1][x]$. Ta duyệt các thửa theo thứ tự BFS ngược (con trước, cha sau) để không cần đệ quy. Mỗi bờ tốn $O(H^2)$ nên tổng $O(N \cdot H^2)$.
Mô phỏng dưới đây chạy QHĐ trên một cây nhỏ: mỗi bước xử lý một thửa (từ lá lên gốc), bảng hiện các giá trị $f$ đã tính.
Ví dụ nhanh:
Trong code, nếu các bờ không tạo thành cây thì quay về vét cạn (Cách 1).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, H;
vector<vector<ll>> c;
vector<int> U, V, D, h;
vector<ll> W;
ll best = LLONG_MAX;
void tryAll(int i) { // Cach 1: vet can
if (i == n) {
ll cost = 0;
for (int k = 0; k < n; k++) cost += c[k][h[k]];
for (int e = 0; e < m; e++) cost += W[e] * max(0, abs(h[U[e]] - h[V[e]]) - D[e]);
best = min(best, cost);
return;
}
for (int x = 0; x <= H; x++) { h[i] = x; tryAll(i + 1); }
}
ll pen(int e, int x, int y) { return W[e] * max(0, abs(x - y) - D[e]); }
bool tree(ll &ans) { // Cach 2: QHD tren cay (neu cac bo tao thanh cay)
if (m != n - 1) return false;
vector<vector<pair<int, int>>> g(n);
for (int e = 0; e < m; e++) { g[U[e]].push_back({V[e], e}); g[V[e]].push_back({U[e], e}); }
vector<int> ord = {0}, par(n, -1), pe(n, -1), seen(n, 0);
seen[0] = 1;
for (int i = 0; i < (int)ord.size(); i++)
for (auto [v, e] : g[ord[i]]) if (!seen[v]) { seen[v] = 1; par[v] = ord[i]; pe[v] = e; ord.push_back(v); }
if ((int)ord.size() != n) return false;
// f[v][x]: chi phi nho nhat cua cay con goc v khi thua v co muc nuoc x
vector<vector<ll>> f(n, vector<ll>(H + 1, 0));
for (int i = n - 1; i >= 0; i--) {
int v = ord[i];
for (int x = 0; x <= H; x++) f[v][x] += c[v][x];
if (i == 0) break;
for (int y = 0; y <= H; y++) { // dong gop cho cha khi cha co muc nuoc y
ll b = LLONG_MAX;
for (int x = 0; x <= H; x++) b = min(b, f[v][x] + pen(pe[v], x, y));
f[par[v]][y] += b;
}
}
ans = *min_element(f[0].begin(), f[0].end());
return true;
}
int main() {
scanf("%d %d %d", &n, &m, &H);
c.assign(n, vector<ll>(H + 1));
for (int i = 0; i < n; i++) for (int x = 0; x <= H; x++) scanf("%lld", &c[i][x]);
U.resize(m); V.resize(m); D.resize(m); W.resize(m); h.assign(n, 0);
for (int e = 0; e < m; e++) { scanf("%d %d %lld %d", &U[e], &V[e], &W[e], &D[e]); U[e]--; V[e]--; }
ll ans;
if (!tree(ans)) { tryAll(0); ans = best; }
printf("%lld\n", ans);
return 0;
}import sys
from itertools import product
def brute(n, H, c, edges): # Cach 1: vet can
best = None
for h in product(range(H + 1), repeat=n):
cost = 0
for i in range(n):
cost += c[i][h[i]]
for u, v, w, d in edges:
diff = abs(h[u] - h[v]) - d
if diff > 0:
cost += w * diff
if best is None or cost < best:
best = cost
return best
def tree(n, H, c, edges): # Cach 2: QHD tren cay; tra ve None neu khong phai cay
if len(edges) != n - 1:
return None
g = [[] for _ in range(n)]
for e, (u, v, w, d) in enumerate(edges):
g[u].append((v, e)); g[v].append((u, e))
order = [0]; par = [-1] * n; pe = [-1] * n; seen = [False] * n
seen[0] = True
for u in order:
for v, e in g[u]:
if not seen[v]:
seen[v] = True; par[v] = u; pe[v] = e; order.append(v)
if len(order) != n:
return None
# f[v][x]: chi phi nho nhat cua cay con goc v khi thua v co muc nuoc x
f = [[0] * (H + 1) for _ in range(n)]
for i in range(n - 1, -1, -1):
v = order[i]; fv = f[v]; cv = c[v]
for x in range(H + 1):
fv[x] += cv[x]
if i == 0:
break
_, _, w, d = edges[pe[v]]; fp = f[par[v]]
for y in range(H + 1): # dong gop cho cha khi cha co muc nuoc y
b = None
for x in range(H + 1):
diff = abs(x - y) - d
val = fv[x] + (w * diff if diff > 0 else 0)
if b is None or val < b:
b = val
fp[y] += b
return min(f[0])
def main():
data = sys.stdin.buffer.read().split()
n, m, H = int(data[0]), int(data[1]), int(data[2])
p = 3
c = []
for i in range(n):
c.append([int(x) for x in data[p:p + H + 1]]); p += H + 1
edges = []
for _ in range(m):
u, v, w, d = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]), int(data[p + 3]); p += 4
edges.append((u, v, w, d))
ans = tree(n, H, c, edges)
if ans is None:
ans = brute(n, H, c, edges)
print(ans)
main()Không gian$O(N \cdot H)$
Thời gian$O(N \cdot H^2)$ khi là cây
Vì sao không mở rộng được cho đồ thị có chu trình?
QHĐ trên cây dựa vào việc bỏ thửa $v$ đi thì các cây con độc lập với nhau. Khi các bờ tạo thành chu trình (cánh đồng dạng lưới chẳng hạn), các thửa ràng buộc vòng tròn lẫn nhau, không còn thứ tự "con trước cha sau" nào cả. Ta cần một công cụ khác hẳn.Cách 3H = 1: mỗi thửa "khô" hoặc "ngập" – lát cắt hẹp nhất, Dinic O(V²E) với V = N + 2 · 45%
Khi $H = 1$, mỗi thửa chỉ có hai lựa chọn: khô ($h = 0$) hoặc ngập ($h = 1$). Một bờ chỉ có thể tốn tiền khi $d = 0$ và hai thửa khác trạng thái (tốn $w$); bờ có $d \ge 1$ không bao giờ tốn gì vì chênh lệch tối đa là $1$.
Bài toán "chia các đối tượng thành hai phe, mỗi đối tượng có chi phí riêng cho từng phe, mỗi cặp bị phạt nếu khác phe" là bài toán lát cắt hẹp nhất kinh điển. Dựng đồ thị có hướng:
- một đỉnh nguồn $s$, một đỉnh đích $t$, mỗi thửa $i$ một đỉnh;
- cạnh $s \to i$ sức chứa $c_{i,0}$ và cạnh $i \to t$ sức chứa $c_{i,1}$;
- mỗi bờ $u - v$ có $d = 0$: hai cạnh $u \to v$ và $v \to u$, cùng sức chứa $w$.
Một lát cắt chia các đỉnh thành phía $S$ (chứa $s$) và phía $T$ (chứa $t$); giá trị lát cắt là tổng sức chứa các cạnh đi từ $S$ sang $T$. Ta quy ước: thửa ở phía $S$ là ngập, ở phía $T$ là khô. Khi đó:
- thửa khô ($i \in T$): cạnh $s \to i$ bị cắt, tốn $c_{i,0}$ ✓; thửa ngập ($i \in S$): cạnh $i \to t$ bị cắt, tốn $c_{i,1}$ ✓;
- bờ $u - v$: nếu hai thửa khác phía thì đúng một trong hai cạnh $u \to v$, $v \to u$ đi từ $S$ sang $T$, tốn $w$ ✓; cùng phía thì không tốn ✓.
Vậy mỗi cách chọn ↔ một lát cắt có giá trị bằng đúng tổng chi phí, và đáp án = lát cắt hẹp nhất = luồng cực đại từ $s$ tới $t$ (định lý Ford–Fulkerson). Ta tính luồng cực đại bằng thuật toán Dinic: lặp lại (1) BFS từ $s$ trên đồ thị thặng dư để chia tầng, (2) DFS đẩy luồng chỉ theo các cạnh đi từ tầng $k$ sang tầng $k + 1$, cho tới khi không còn đường từ $s$ tới $t$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
struct Edge { int to; ll cap; };
vector<Edge> E;
vector<vector<int>> adj;
vector<int> lvl, it;
void init(int V) { E.clear(); adj.assign(V, {}); lvl.assign(V, 0); it.assign(V, 0); }
void addEdge(int u, int v, ll c) {
adj[u].push_back(E.size()); E.push_back({v, c});
adj[v].push_back(E.size()); E.push_back({u, 0});
}
bool bfs(int s, int t) { // Dinic: chia tang theo khoang cach tu s
fill(lvl.begin(), lvl.end(), -1);
queue<int> q; q.push(s); lvl[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int id : adj[u])
if (E[id].cap > 0 && lvl[E[id].to] < 0) { lvl[E[id].to] = lvl[u] + 1; q.push(E[id].to); }
}
return lvl[t] >= 0;
}
ll dfs(int u, int t, ll f) { // day luong tren do thi tang
if (u == t) return f;
for (int &i = it[u]; i < (int)adj[u].size(); i++) {
int id = adj[u][i], v = E[id].to;
if (E[id].cap > 0 && lvl[v] == lvl[u] + 1) {
ll got = dfs(v, t, min(f, E[id].cap));
if (got > 0) { E[id].cap -= got; E[id ^ 1].cap += got; return got; }
}
}
return 0;
}
ll maxflow(int s, int t) {
ll flow = 0;
while (bfs(s, t)) {
fill(it.begin(), it.end(), 0);
while (ll f = dfs(s, t, INF)) flow += f;
}
return flow;
}
int n, m, H;
vector<vector<ll>> c;
vector<int> U, V, D, h;
vector<ll> W;
ll best = LLONG_MAX;
void tryAll(int i) { // Cach 1: vet can
if (i == n) {
ll cost = 0;
for (int k = 0; k < n; k++) cost += c[k][h[k]];
for (int e = 0; e < m; e++) cost += W[e] * max(0, abs(h[U[e]] - h[V[e]]) - D[e]);
best = min(best, cost);
return;
}
for (int x = 0; x <= H; x++) { h[i] = x; tryAll(i + 1); }
}
ll pen(int e, int x, int y) { return W[e] * max(0, abs(x - y) - D[e]); }
bool tree(ll &ans) { // Cach 2: QHD tren cay (neu cac bo tao thanh cay)
if (m != n - 1) return false;
vector<vector<pair<int, int>>> g(n);
for (int e = 0; e < m; e++) { g[U[e]].push_back({V[e], e}); g[V[e]].push_back({U[e], e}); }
vector<int> ord = {0}, par(n, -1), pe(n, -1), seen(n, 0);
seen[0] = 1;
for (int i = 0; i < (int)ord.size(); i++)
for (auto [v, e] : g[ord[i]]) if (!seen[v]) { seen[v] = 1; par[v] = ord[i]; pe[v] = e; ord.push_back(v); }
if ((int)ord.size() != n) return false;
// f[v][x]: chi phi nho nhat cua cay con goc v khi thua v co muc nuoc x
vector<vector<ll>> f(n, vector<ll>(H + 1, 0));
for (int i = n - 1; i >= 0; i--) {
int v = ord[i];
for (int x = 0; x <= H; x++) f[v][x] += c[v][x];
if (i == 0) break;
for (int y = 0; y <= H; y++) { // dong gop cho cha khi cha co muc nuoc y
ll b = LLONG_MAX;
for (int x = 0; x <= H; x++) b = min(b, f[v][x] + pen(pe[v], x, y));
f[par[v]][y] += b;
}
}
ans = *min_element(f[0].begin(), f[0].end());
return true;
}
ll cutH1() { // Cach 3: H = 1, moi thua chi "kho" (0) hoac "ngap" (1)
int s = 0, t = n + 1;
init(t + 1);
for (int i = 0; i < n; i++) { addEdge(s, i + 1, c[i][0]); addEdge(i + 1, t, c[i][1]); }
for (int e = 0; e < m; e++) if (D[e] == 0) { addEdge(U[e] + 1, V[e] + 1, W[e]); addEdge(V[e] + 1, U[e] + 1, W[e]); }
return maxflow(s, t);
}
int main() {
scanf("%d %d %d", &n, &m, &H);
c.assign(n, vector<ll>(H + 1));
for (int i = 0; i < n; i++) for (int x = 0; x <= H; x++) scanf("%lld", &c[i][x]);
U.resize(m); V.resize(m); D.resize(m); W.resize(m); h.assign(n, 0);
for (int e = 0; e < m; e++) { scanf("%d %d %lld %d", &U[e], &V[e], &W[e], &D[e]); U[e]--; V[e]--; }
ll ans;
if (H == 1) ans = cutH1();
else if (!tree(ans)) { tryAll(0); ans = best; }
printf("%lld\n", ans);
return 0;
}import sys
from itertools import product
def brute(n, H, c, edges): # Cach 1: vet can
best = None
for h in product(range(H + 1), repeat=n):
cost = 0
for i in range(n):
cost += c[i][h[i]]
for u, v, w, d in edges:
diff = abs(h[u] - h[v]) - d
if diff > 0:
cost += w * diff
if best is None or cost < best:
best = cost
return best
def tree(n, H, c, edges): # Cach 2: QHD tren cay; tra ve None neu khong phai cay
if len(edges) != n - 1:
return None
g = [[] for _ in range(n)]
for e, (u, v, w, d) in enumerate(edges):
g[u].append((v, e)); g[v].append((u, e))
order = [0]; par = [-1] * n; pe = [-1] * n; seen = [False] * n
seen[0] = True
for u in order:
for v, e in g[u]:
if not seen[v]:
seen[v] = True; par[v] = u; pe[v] = e; order.append(v)
if len(order) != n:
return None
# f[v][x]: chi phi nho nhat cua cay con goc v khi thua v co muc nuoc x
f = [[0] * (H + 1) for _ in range(n)]
for i in range(n - 1, -1, -1):
v = order[i]; fv = f[v]; cv = c[v]
for x in range(H + 1):
fv[x] += cv[x]
if i == 0:
break
_, _, w, d = edges[pe[v]]; fp = f[par[v]]
for y in range(H + 1): # dong gop cho cha khi cha co muc nuoc y
b = None
for x in range(H + 1):
diff = abs(x - y) - d
val = fv[x] + (w * diff if diff > 0 else 0)
if b is None or val < b:
b = val
fp[y] += b
return min(f[0])
def max_flow(V, s, t, arcs): # Dinic (khong de quy) tren danh sach cung (u, v, suc chua)
INF = 4 * 10 ** 18
head = [-1] * V; to = []; cap = []; nxt = []
for u, v, c in arcs:
to.append(v); cap.append(c); nxt.append(head[u]); head[u] = len(to) - 1
to.append(u); cap.append(0); nxt.append(head[v]); head[v] = len(to) - 1
flow = 0
while True:
lvl = [-1] * V; lvl[s] = 0; q = [s]
for u in q:
e = head[u]; lu = lvl[u] + 1
while e != -1:
if cap[e] > 0 and lvl[to[e]] < 0:
lvl[to[e]] = lu; q.append(to[e])
e = nxt[e]
if lvl[t] < 0:
return flow
it = head[:]
path = []; u = s
while True:
if u == t:
f = INF
for e in path:
if cap[e] < f: f = cap[e]
k = -1
for i in range(len(path)):
e = path[i]; cap[e] -= f; cap[e ^ 1] += f
if k < 0 and cap[e] == 0: k = i
flow += f
del path[k:]
u = to[path[-1]] if path else s
continue
e = it[u]; lu = lvl[u] + 1
while e != -1 and (cap[e] <= 0 or lvl[to[e]] != lu):
e = nxt[e]
it[u] = e
if e == -1:
if u == s:
break
lvl[u] = -1
e = path.pop(); u = to[e ^ 1]
else:
path.append(e); u = to[e]
def cut_h1(n, c, edges): # Cach 3: H = 1, moi thua chi "kho" (0) hoac "ngap" (1)
s, t = 0, n + 1
arcs = []
for i in range(n):
arcs.append((s, i + 1, c[i][0])); arcs.append((i + 1, t, c[i][1]))
for u, v, w, d in edges:
if d == 0:
arcs.append((u + 1, v + 1, w)); arcs.append((v + 1, u + 1, w))
return max_flow(t + 1, s, t, arcs)
def main():
data = sys.stdin.buffer.read().split()
n, m, H = int(data[0]), int(data[1]), int(data[2])
p = 3
c = []
for i in range(n):
c.append([int(x) for x in data[p:p + H + 1]]); p += H + 1
edges = []
for _ in range(m):
u, v, w, d = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]), int(data[p + 3]); p += 4
edges.append((u, v, w, d))
if H == 1:
ans = cut_h1(n, c, edges)
else:
ans = tree(n, H, c, edges)
if ans is None:
ans = brute(n, H, c, edges)
print(ans)
main()Không gian$O(N + M)$
Thời gianDinic trên $N + 2$ đỉnh, $2N + 2M$ cạnh
Cách 4Mọi d = 0: chuỗi mức nước – Dinic trên V = NH + 2 đỉnh, E = O(NH + MH) cạnh · 70%
Bây giờ mỗi thửa có $H + 1$ lựa chọn. Ý tưởng: thay vì một câu hỏi "ngập hay khô", hỏi $H$ câu hỏi có/không: "mực nước thửa $i$ có ít nhất $j$ không?" với $j = 1, 2, \ldots, H$. Mỗi câu hỏi là một đỉnh $(i, j)$; trả lời "có" ⇔ đỉnh nằm phía $S$.
Nếu thửa $i$ có mực nước $h$, các câu trả lời là "có, có, …, có" ($h$ lần) rồi "không, …, không". Dựng chuỗi cho thửa $i$ (xem hình ở phần mở đầu):
- $s \to (i, 1)$ sức chứa $c_{i,0}$; $(i, j) \to (i, j + 1)$ sức chứa $c_{i,j}$; $(i, H) \to t$ sức chứa $c_{i,H}$. Phía $S$ của chuỗi là $(i, 1), \ldots, (i, h)$ nên chỉ đúng cạnh mang $c_{i,h}$ bị cắt ✓.
- Cạnh ngược $(i, j + 1) \to (i, j)$ sức chứa vô cùng: nếu có "lỗ hổng" ($(i, j + 1)$ phía $S$ mà $(i, j)$ phía $T$) thì cạnh vô cùng bị cắt – lát cắt hẹp nhất không bao giờ chọn như vậy. Nhờ đó mỗi lát cắt hữu hạn ứng với đúng một cách chọn mực nước.
Còn bờ $u - v$ (với $d = 0$): với mỗi mức $j$, thêm hai cạnh $(u, j) \to (v, j)$ và $(v, j) \to (u, j)$ sức chứa $w$. Ở mức $j$, hai đỉnh khác phía ⇔ đúng một trong hai câu "$h_u \ge j$", "$h_v \ge j$" đúng ⇔ $\min(h_u, h_v) < j \le \max(h_u, h_v)$. Có đúng $|h_u - h_v|$ mức như vậy, mỗi mức cắt đúng một cạnh sức chứa $w$: tổng $w \cdot |h_u - h_v|$ ✓.
Kết luận
Lát cắt hẹp nhất trên đồ thị $N \cdot H + 2$ đỉnh này đúng bằng chi phí nhỏ nhất. Cách 3 chính là trường hợp riêng $H = 1$.#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
struct Edge { int to; ll cap; };
vector<Edge> E;
vector<vector<int>> adj;
vector<int> lvl, it;
void init(int V) { E.clear(); adj.assign(V, {}); lvl.assign(V, 0); it.assign(V, 0); }
void addEdge(int u, int v, ll c) {
adj[u].push_back(E.size()); E.push_back({v, c});
adj[v].push_back(E.size()); E.push_back({u, 0});
}
bool bfs(int s, int t) { // Dinic: chia tang theo khoang cach tu s
fill(lvl.begin(), lvl.end(), -1);
queue<int> q; q.push(s); lvl[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int id : adj[u])
if (E[id].cap > 0 && lvl[E[id].to] < 0) { lvl[E[id].to] = lvl[u] + 1; q.push(E[id].to); }
}
return lvl[t] >= 0;
}
ll dfs(int u, int t, ll f) { // day luong tren do thi tang
if (u == t) return f;
for (int &i = it[u]; i < (int)adj[u].size(); i++) {
int id = adj[u][i], v = E[id].to;
if (E[id].cap > 0 && lvl[v] == lvl[u] + 1) {
ll got = dfs(v, t, min(f, E[id].cap));
if (got > 0) { E[id].cap -= got; E[id ^ 1].cap += got; return got; }
}
}
return 0;
}
ll maxflow(int s, int t) {
ll flow = 0;
while (bfs(s, t)) {
fill(it.begin(), it.end(), 0);
while (ll f = dfs(s, t, INF)) flow += f;
}
return flow;
}
int n, m, H;
vector<vector<ll>> c;
vector<int> U, V, D, h;
vector<ll> W;
ll best = LLONG_MAX;
void tryAll(int i) { // Cach 1: vet can
if (i == n) {
ll cost = 0;
for (int k = 0; k < n; k++) cost += c[k][h[k]];
for (int e = 0; e < m; e++) cost += W[e] * max(0, abs(h[U[e]] - h[V[e]]) - D[e]);
best = min(best, cost);
return;
}
for (int x = 0; x <= H; x++) { h[i] = x; tryAll(i + 1); }
}
ll pen(int e, int x, int y) { return W[e] * max(0, abs(x - y) - D[e]); }
bool tree(ll &ans) { // Cach 2: QHD tren cay (neu cac bo tao thanh cay)
if (m != n - 1) return false;
vector<vector<pair<int, int>>> g(n);
for (int e = 0; e < m; e++) { g[U[e]].push_back({V[e], e}); g[V[e]].push_back({U[e], e}); }
vector<int> ord = {0}, par(n, -1), pe(n, -1), seen(n, 0);
seen[0] = 1;
for (int i = 0; i < (int)ord.size(); i++)
for (auto [v, e] : g[ord[i]]) if (!seen[v]) { seen[v] = 1; par[v] = ord[i]; pe[v] = e; ord.push_back(v); }
if ((int)ord.size() != n) return false;
// f[v][x]: chi phi nho nhat cua cay con goc v khi thua v co muc nuoc x
vector<vector<ll>> f(n, vector<ll>(H + 1, 0));
for (int i = n - 1; i >= 0; i--) {
int v = ord[i];
for (int x = 0; x <= H; x++) f[v][x] += c[v][x];
if (i == 0) break;
for (int y = 0; y <= H; y++) { // dong gop cho cha khi cha co muc nuoc y
ll b = LLONG_MAX;
for (int x = 0; x <= H; x++) b = min(b, f[v][x] + pen(pe[v], x, y));
f[par[v]][y] += b;
}
}
ans = *min_element(f[0].begin(), f[0].end());
return true;
}
ll chain() { // Cach 4: moi bo co d = 0 (hoac H = 1): chuoi H dinh cho moi thua
int s = 0, t = n * H + 1;
init(t + 1);
auto id = [&](int i, int j) { return i * H + j; }; // "thua i co muc nuoc >= j"
for (int i = 0; i < n; i++) {
addEdge(s, id(i, 1), c[i][0]);
for (int j = 1; j < H; j++) addEdge(id(i, j), id(i, j + 1), c[i][j]);
addEdge(id(i, H), t, c[i][H]);
for (int j = 1; j < H; j++) addEdge(id(i, j + 1), id(i, j), INF);
}
for (int e = 0; e < m; e++) if (D[e] == 0)
for (int j = 1; j <= H; j++) { // muc j cua hai thua bi tach => phat W
addEdge(id(U[e], j), id(V[e], j), W[e]);
addEdge(id(V[e], j), id(U[e], j), W[e]);
}
return maxflow(s, t);
}
int main() {
scanf("%d %d %d", &n, &m, &H);
c.assign(n, vector<ll>(H + 1));
for (int i = 0; i < n; i++) for (int x = 0; x <= H; x++) scanf("%lld", &c[i][x]);
U.resize(m); V.resize(m); D.resize(m); W.resize(m); h.assign(n, 0);
for (int e = 0; e < m; e++) { scanf("%d %d %lld %d", &U[e], &V[e], &W[e], &D[e]); U[e]--; V[e]--; }
ll ans;
bool allZero = true;
for (int e = 0; e < m; e++) if (D[e] != 0) allZero = false;
if (H == 1 || allZero) ans = chain();
else if (!tree(ans)) { tryAll(0); ans = best; }
printf("%lld\n", ans);
return 0;
}import sys
from itertools import product
def brute(n, H, c, edges): # Cach 1: vet can
best = None
for h in product(range(H + 1), repeat=n):
cost = 0
for i in range(n):
cost += c[i][h[i]]
for u, v, w, d in edges:
diff = abs(h[u] - h[v]) - d
if diff > 0:
cost += w * diff
if best is None or cost < best:
best = cost
return best
def tree(n, H, c, edges): # Cach 2: QHD tren cay; tra ve None neu khong phai cay
if len(edges) != n - 1:
return None
g = [[] for _ in range(n)]
for e, (u, v, w, d) in enumerate(edges):
g[u].append((v, e)); g[v].append((u, e))
order = [0]; par = [-1] * n; pe = [-1] * n; seen = [False] * n
seen[0] = True
for u in order:
for v, e in g[u]:
if not seen[v]:
seen[v] = True; par[v] = u; pe[v] = e; order.append(v)
if len(order) != n:
return None
# f[v][x]: chi phi nho nhat cua cay con goc v khi thua v co muc nuoc x
f = [[0] * (H + 1) for _ in range(n)]
for i in range(n - 1, -1, -1):
v = order[i]; fv = f[v]; cv = c[v]
for x in range(H + 1):
fv[x] += cv[x]
if i == 0:
break
_, _, w, d = edges[pe[v]]; fp = f[par[v]]
for y in range(H + 1): # dong gop cho cha khi cha co muc nuoc y
b = None
for x in range(H + 1):
diff = abs(x - y) - d
val = fv[x] + (w * diff if diff > 0 else 0)
if b is None or val < b:
b = val
fp[y] += b
return min(f[0])
def max_flow(V, s, t, arcs): # Dinic (khong de quy) tren danh sach cung (u, v, suc chua)
INF = 4 * 10 ** 18
head = [-1] * V; to = []; cap = []; nxt = []
for u, v, c in arcs:
to.append(v); cap.append(c); nxt.append(head[u]); head[u] = len(to) - 1
to.append(u); cap.append(0); nxt.append(head[v]); head[v] = len(to) - 1
flow = 0
while True:
lvl = [-1] * V; lvl[s] = 0; q = [s]
for u in q:
e = head[u]; lu = lvl[u] + 1
while e != -1:
if cap[e] > 0 and lvl[to[e]] < 0:
lvl[to[e]] = lu; q.append(to[e])
e = nxt[e]
if lvl[t] < 0:
return flow
it = head[:]
path = []; u = s
while True:
if u == t:
f = INF
for e in path:
if cap[e] < f: f = cap[e]
k = -1
for i in range(len(path)):
e = path[i]; cap[e] -= f; cap[e ^ 1] += f
if k < 0 and cap[e] == 0: k = i
flow += f
del path[k:]
u = to[path[-1]] if path else s
continue
e = it[u]; lu = lvl[u] + 1
while e != -1 and (cap[e] <= 0 or lvl[to[e]] != lu):
e = nxt[e]
it[u] = e
if e == -1:
if u == s:
break
lvl[u] = -1
e = path.pop(); u = to[e ^ 1]
else:
path.append(e); u = to[e]
def chain(n, H, c, edges): # Cach 4: moi bo co d = 0 (hoac H = 1): chuoi H dinh cho moi thua
INF = 4 * 10 ** 18
s, t = 0, n * H + 1
arcs = []
for i in range(n): # dinh i * H + j: "thua i co muc nuoc >= j"
b = i * H
arcs.append((s, b + 1, c[i][0]))
for j in range(1, H):
arcs.append((b + j, b + j + 1, c[i][j]))
arcs.append((b + H, t, c[i][H]))
for j in range(1, H):
arcs.append((b + j + 1, b + j, INF))
for u, v, w, d in edges:
if d == 0:
for j in range(1, H + 1): # muc j cua hai thua bi tach => phat w
arcs.append((u * H + j, v * H + j, w)); arcs.append((v * H + j, u * H + j, w))
return max_flow(t + 1, s, t, arcs)
def main():
data = sys.stdin.buffer.read().split()
n, m, H = int(data[0]), int(data[1]), int(data[2])
p = 3
c = []
for i in range(n):
c.append([int(x) for x in data[p:p + H + 1]]); p += H + 1
edges = []
for _ in range(m):
u, v, w, d = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]), int(data[p + 3]); p += 4
edges.append((u, v, w, d))
if H == 1 or all(d == 0 for _, _, _, d in edges):
ans = chain(n, H, c, edges)
else:
ans = tree(n, H, c, edges)
if ans is None:
ans = brute(n, H, c, edges)
print(ans)
main()Không gian$O(N H + M H)$
Thời gianDinic trên $N H + 2$ đỉnh, $O(N H + M H)$ cạnh
Cách 5Ngưỡng d bất kỳ: cạnh lệch tầng – Dinic trên V = NH + 2 đỉnh, E = O(NH + MH) cạnh · 100%
Bờ có ngưỡng $d$ chỉ phạt phần chênh lệch vượt quá $d$: $w \cdot \max(0, |h_u - h_v| - d)$. Tách làm hai chiều: $\max(0, h_u - h_v - d)$ (thửa $u$ cao hơn) và $\max(0, h_v - h_u - d)$ (thửa $v$ cao hơn) – tổng hai số này đúng bằng $\max(0, |h_u - h_v| - d)$ vì tối đa một số khác $0$.
Với chiều "$u$ cao hơn", thêm các cạnh lệch tầng $(u, j) \to (v, j - d)$ sức chứa $w$, với $j = d + 1, \ldots, H$. Cạnh này bị cắt ⇔ $(u, j) \in S$ và $(v, j - d) \in T$ ⇔ $h_u \ge j$ và $h_v < j - d$ ⇔ $h_v + d < j \le h_u$. Số mức $j$ như vậy đúng bằng $\max(0, h_u - h_v - d)$ ✓. Chiều ngược lại thêm $(v, j) \to (u, j - d)$. Khi $d = 0$ ta trở về đúng Cách 4.
Hai lỗi rất dễ mắc
- Quên một chiều: chỉ thêm $(u, j) \to (v, j - d)$ mà quên $(v, j) \to (u, j - d)$ thì chỉ phạt khi thửa $u$ cao hơn.
- Lệch một tầng: nối $(u, j) \to (v, j - d + 1)$ là phạt cả khi chênh lệch bằng $d$ – sai với đề ("không vượt quá $d_k$ thì không tốn gì").
Mô phỏng sau minh hoạ hai chuỗi của một con bờ: em chọn $H$, $d$ và mực nước hai thửa, mô phỏng sẽ duyệt từng mức $j$ và tô đỏ các cạnh lệch tầng bị cắt. Số cạnh bị cắt luôn bằng $\max(0, |h_u - h_v| - d)$.
Ví dụ nhanh:
Tổng kết cách dựng đồ thị (đây chính là lời giải 100%):
- Đỉnh: $s$, $t$ và $(i, j)$ với $1 \le i \le N$, $1 \le j \le H$ – tổng $N H + 2 \le 6002$ đỉnh.
- Mỗi thửa: chuỗi $s \to (i, 1) \to \cdots \to (i, H) \to t$ với sức chứa $c_{i,0}, \ldots, c_{i,H}$, cộng các cạnh ngược vô cùng.
- Mỗi bờ $(u, v, w, d)$: với $j = d + 1, \ldots, H$, hai cạnh $(u, j) \to (v, j - d)$ và $(v, j) \to (u, j - d)$, sức chứa $w$.
- Đáp án = luồng cực đại từ $s$ tới $t$ (Dinic). Số cạnh tối đa khoảng $N(2H + 1) + 2MH \approx 72\,000$ – Dinic chạy rất nhanh.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;
struct Edge { int to; ll cap; };
vector<Edge> E;
vector<vector<int>> adj;
vector<int> lvl, it;
void addEdge(int u, int v, ll c) {
adj[u].push_back(E.size()); E.push_back({v, c});
adj[v].push_back(E.size()); E.push_back({u, 0});
}
bool bfs(int s, int t) { // Dinic: chia tang theo khoang cach tu s
fill(lvl.begin(), lvl.end(), -1);
queue<int> q; q.push(s); lvl[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int id : adj[u])
if (E[id].cap > 0 && lvl[E[id].to] < 0) { lvl[E[id].to] = lvl[u] + 1; q.push(E[id].to); }
}
return lvl[t] >= 0;
}
ll dfs(int u, int t, ll f) { // day luong tren do thi tang
if (u == t) return f;
for (int &i = it[u]; i < (int)adj[u].size(); i++) {
int id = adj[u][i], v = E[id].to;
if (E[id].cap > 0 && lvl[v] == lvl[u] + 1) {
ll got = dfs(v, t, min(f, E[id].cap));
if (got > 0) { E[id].cap -= got; E[id ^ 1].cap += got; return got; }
}
}
return 0;
}
int main() {
int n, m, H;
scanf("%d %d %d", &n, &m, &H);
int s = 0, t = n * H + 1;
adj.assign(t + 1, {}); lvl.assign(t + 1, 0); it.assign(t + 1, 0);
auto id = [&](int i, int j) { return (i - 1) * H + j; }; // dinh (i, j): "thua i co muc nuoc >= j"
for (int i = 1; i <= n; i++) {
vector<ll> c(H + 1);
for (int h = 0; h <= H; h++) scanf("%lld", &c[h]);
addEdge(s, id(i, 1), c[0]); // cat canh nay <=> muc nuoc 0
for (int j = 1; j < H; j++) addEdge(id(i, j), id(i, j + 1), c[j]);
addEdge(id(i, H), t, c[H]);
for (int j = 1; j < H; j++) addEdge(id(i, j + 1), id(i, j), INF); // cam cat chuoi hai lan
}
for (int k = 0; k < m; k++) {
int u, v; ll w; int d;
scanf("%d %d %lld %d", &u, &v, &w, &d);
for (int j = d + 1; j <= H; j++) { // h_u >= j va h_v < j - d => phat w
addEdge(id(u, j), id(v, j - d), w);
addEdge(id(v, j), id(u, j - d), w);
}
}
ll flow = 0;
while (bfs(s, t)) {
fill(it.begin(), it.end(), 0);
while (ll f = dfs(s, t, INF)) flow += f;
}
printf("%lld\n", flow);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, H = int(data[0]), int(data[1]), int(data[2])
INF = 4 * 10 ** 18
s, t = 0, n * H + 1
V = t + 1
head = [-1] * V
to = []; cap = []; nxt = []
def add_edge(u, v, c):
to.append(v); cap.append(c); nxt.append(head[u]); head[u] = len(to) - 1
to.append(u); cap.append(0); nxt.append(head[v]); head[v] = len(to) - 1
p = 3
for i in range(1, n + 1): # dinh (i, j) = (i - 1) * H + j: "thua i co muc nuoc >= j"
base = (i - 1) * H
add_edge(s, base + 1, int(data[p])) # cat canh nay <=> muc nuoc 0
for j in range(1, H):
add_edge(base + j, base + j + 1, int(data[p + j]))
add_edge(base + H, t, int(data[p + H]))
for j in range(1, H):
add_edge(base + j + 1, base + j, INF) # cam cat chuoi hai lan
p += H + 1
for _ in range(m):
u, v, w, d = int(data[p]), int(data[p + 1]), int(data[p + 2]), int(data[p + 3]); p += 4
bu = (u - 1) * H; bv = (v - 1) * H
for j in range(d + 1, H + 1): # h_u >= j va h_v < j - d => phat w
add_edge(bu + j, bv + j - d, w)
add_edge(bv + j, bu + j - d, w)
flow = 0
while True:
lvl = [-1] * V; lvl[s] = 0; q = [s] # Dinic: chia tang bang BFS
for u in q:
e = head[u]; lu = lvl[u] + 1
while e != -1:
if cap[e] > 0 and lvl[to[e]] < 0:
lvl[to[e]] = lu; q.append(to[e])
e = nxt[e]
if lvl[t] < 0:
break
it = head[:]
path = []; u = s
while True: # DFS khong de quy tren do thi tang
if u == t:
f = INF
for e in path:
if cap[e] < f: f = cap[e]
k = -1
for i in range(len(path)):
e = path[i]; cap[e] -= f; cap[e ^ 1] += f
if k < 0 and cap[e] == 0: k = i
flow += f
del path[k:] # lui ve dau canh bao hoa dau tien
u = to[path[-1]] if path else s
continue
e = it[u]; lu = lvl[u] + 1
while e != -1 and (cap[e] <= 0 or lvl[to[e]] != lu):
e = nxt[e]
it[u] = e
if e == -1: # ngo cut: lui lai
if u == s:
break
lvl[u] = -1
e = path.pop(); u = to[e ^ 1]
else:
path.append(e); u = to[e]
print(flow)
main()Không gian$O(N H + M H)$
Thời gianDinic trên $O(N H)$ đỉnh, $O(N H + M H)$ cạnh
Chạy tay từng dòng code C++ trên ví dụ đề: bảng bên phải hiện sức chứa còn lại (thặng dư) trên các cạnh của chuỗi mỗi thửa; mỗi lần DFS tìm được một đường tăng luồng, mô phỏng in ra đường đi đó. Ở bước cuối, các đỉnh còn tới được từ $s$ cho biết mực nước tối ưu của từng thửa.
C++▶ Chạy tay từng dòng codeDựng chuỗi mức nước, thêm cạnh lệch tầng, rồi chạy Dinic.
Dữ liệu mẫu:
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4const ll INF = (ll)4e18;
5struct Edge { int to; ll cap; };
6vector<Edge> E;
7vector<vector<int>> adj;
8vector<int> lvl, it;
9void addEdge(int u, int v, ll c) {
10 adj[u].push_back(E.size()); E.push_back({v, c});
11 adj[v].push_back(E.size()); E.push_back({u, 0});
12}
13bool bfs(int s, int t) { // Dinic: chia tang theo khoang cach tu s
14 fill(lvl.begin(), lvl.end(), -1);
15 queue<int> q; q.push(s); lvl[s] = 0;
16 while (!q.empty()) {
17 int u = q.front(); q.pop();
18 for (int id : adj[u])
19 if (E[id].cap > 0 && lvl[E[id].to] < 0) { lvl[E[id].to] = lvl[u] + 1; q.push(E[id].to); }
20 }
21 return lvl[t] >= 0;
22}
23ll dfs(int u, int t, ll f) { // day luong tren do thi tang
24 if (u == t) return f;
25 for (int &i = it[u]; i < (int)adj[u].size(); i++) {
26 int id = adj[u][i], v = E[id].to;
27 if (E[id].cap > 0 && lvl[v] == lvl[u] + 1) {
28 ll got = dfs(v, t, min(f, E[id].cap));
29 if (got > 0) { E[id].cap -= got; E[id ^ 1].cap += got; return got; }
30 }
31 }
32 return 0;
33}
34int main() {
35 int n, m, H;
36 scanf("%d %d %d", &n, &m, &H);
37 int s = 0, t = n * H + 1;
38 adj.assign(t + 1, {}); lvl.assign(t + 1, 0); it.assign(t + 1, 0);
39 auto id = [&](int i, int j) { return (i - 1) * H + j; }; // dinh (i, j): "thua i co muc nuoc >= j"
40 for (int i = 1; i <= n; i++) {
41 vector<ll> c(H + 1);
42 for (int h = 0; h <= H; h++) scanf("%lld", &c[h]);
43 addEdge(s, id(i, 1), c[0]); // cat canh nay <=> muc nuoc 0
44 for (int j = 1; j < H; j++) addEdge(id(i, j), id(i, j + 1), c[j]);
45 addEdge(id(i, H), t, c[H]);
46 for (int j = 1; j < H; j++) addEdge(id(i, j + 1), id(i, j), INF); // cam cat chuoi hai lan
47 }
48 for (int k = 0; k < m; k++) {
49 int u, v; ll w; int d;
50 scanf("%d %d %lld %d", &u, &v, &w, &d);
51 for (int j = d + 1; j <= H; j++) { // h_u >= j va h_v < j - d => phat w
52 addEdge(id(u, j), id(v, j - d), w);
53 addEdge(id(v, j), id(u, j - d), w);
54 }
55 }
56 ll flow = 0;
57 while (bfs(s, t)) {
58 fill(it.begin(), it.end(), 0);
59 while (ll f = dfs(s, t, INF)) flow += f;
60 }
61 printf("%lld\n", flow);
62 return 0;
63}
Một nhận xét thú vị
Thử bỏ hẳn các cạnh ngược vô cùng thì đáp án trên toàn bộ bộ test của bài vẫn không đổi – lát cắt hẹp nhất có vẻ "tự biết" chỉ cắt mỗi chuỗi một lần. Nhưng chứng minh điều đó không hề đơn giản; còn khi giữ các cạnh vô cùng lại thì lập luận "mỗi lát cắt hữu hạn ↔ một cách chọn mực nước" trở nên hiển nhiên. Trong phòng thi, cứ thêm vào cho chắc!Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 (10%, 9 test) | Sub 2 (15%, 6 test) | Sub 3 (20%, 7 test) | Sub 4 (25%, 7 test) | Sub 5 (30%, 8 test) | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – vét cạn | Đúng | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – QHĐ trên cây | Đúng | Đúng | TLE | TLE | TLE | 25 |
| Cách 3 – lát cắt khi H = 1 | Đúng | Đúng | Đúng | TLE | TLE | 45 |
| Cách 4 – chuỗi mức nước (d = 0) | Đúng | Đúng | Đúng | Đúng | TLE | 70 |
| Cách 5 – cạnh lệch tầng (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | Đúng | 100 |
Sai: dùng int cho sức chứa và tổng luồng | 8/9 | 4/6 | 4/7 | 5/7 | 5/8 | 66,92 |
| Sai: lệch một tầng (phạt cả khi chênh lệch bằng d) | 3/9 | 1/6 | 6/7 | Đúng | 0/8 | 47,98 |
| Sai: tham lam – mỗi thửa lần lượt chọn mức tốt nhất theo hàng xóm | 3/9 | 0/6 | 1/7 | 0/7 | 0/8 | 6,19 |
| Sai: chỉ thêm cạnh lệch tầng một chiều | 2/9 | 0/6 | 0/7 | 0/7 | 0/8 | 2,22 |
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: bộ test có 37 test (9 + 6 + 7 + 7 + 8), mỗi cách đạt đúng số điểm công bố, còn bốn lời giải sai bị bắt như bảng trên. Lời giải chuẩn sol.cpp chạy test lâu nhất chỉ khoảng 0,16 giây; bản Python sol.py cho cùng đáp án trên mọi test (trên CPython khoảng 3,5 giây, các em nên chọn PyPy 3 khi nộp). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian (các cách 1–4 rơi về vét cạn khi gặp test ngoài subtask của mình). Để ý: lời giải tham lam "mỗi thửa chọn mức tốt nhất khi biết hàng xóm" nghe rất hợp lý nhưng chỉ được hơn 6 điểm – các thửa ràng buộc vòng tròn với nhau nên tối ưu cục bộ không phải tối ưu toàn cục. Còn lỗi lệch một tầng thì nguy hiểm ở chỗ nó vẫn đúng trọn subtask 4 (vì d = 0), chỉ lộ ra khi có ngưỡng d > 0 – đọc kỹ chữ "không vượt quá" trong đề nhé!
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 😇
Tự học thuật toán: khó ở đâu?
Đọc xong một bài giải là bước đầu. Phần lớn học sinh tự học sẽ gặp những trở ngại sau:
- 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.
Học cùng thầy Nam Sơn, các trở ngại đó được gỡ bỏ:
- 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