Ta dựng mạng như sau: nối đỉnh nguồn $S$ tới từng ngày $i$ với lưu lượng là $c_i$, và nối các ngày này tới tất cả các đỉnh trên đường đi từ $u$ đến $v$, sau đó nối từng đỉnh $i$ vào đỉnh thu $T$ với lưu lượng bằng $a_i$
Nhưng làm thế này thì số cạnh trên mạng có thể sẽ rất lớn
=> Dùng $HLD$ nén lại các đỉnh thành các đỉnh ảo trên Segment Tree để giảm số lượng cạnh đi, sau đó tìm luồng cực đại trên mạng này
## Thuật toán ngây thơ
Ta dựng một mạng theo quy tắc sau:
- Đỉnh nguồn ($s$) nối đến các đỉnh $\texttt{node}_i$ với sức chứa $a_i$ (số lọ thuốc ở mỗi nhà).
- Với mỗi đỉnh $\texttt{day}_i$ nối các một cung có sức chứa $\infty$ từ các đỉnh $\texttt{node}_j$ với $j$ là các đỉnh đi đến trong ngày $i$.
- Nối các đỉnh $\texttt{day}_i$ với đỉnh thu ($t$) với sức chứa $c_i$ (số lọ thuốc được bán trong ngày $i$)
Dễ thấy, luồng cực đại từ $s-t$ của mạng dựng ra chính là kết quả của bài toán.
## Tối ưu thao tác dựng đồ thị
Để đơn giản hóa, ta trước hết ta sẽ giải bài toán khi những đỉnh được thăm trong ngày thứ $i$ có dạng một đoạn liên tiếp $[u_i, v_i]$.
Vấn đề của thuật toán ngây thơ là số cạnh của mạng quá nhiều nên ta cần một cách dựng đồ thị hữu hiệu hơn.
Ta sử dụng kỹ thuật dựng đồ thị segment tree, mỗi khi cần nối $x$ đến các đỉnh thuộc $[u_i, v_i]$, ta sẽ nối $x$ đến các node trên segment tree. Khi đó số cạnh tối đa chỉ là $\mathcal{O}(\log n)$. Để dễ hình dung, bạn đọc có thể coi hình sau:
[image](https://hackmd.io/_uploads/HkT5Ti3EZe.png)
Ở hình trên, ta đang truy vấn trên đoạn $[2, 5]$, các cung không ghi sức chứa ta quy ước có sức chứa là $\infty$.
Kết hợp với kỹ thuật Heavy Light Decomposition để biểu diễn một đường đi thành dạng mảng, ta sẽ tối ưu số cạnh của mạng chỉ còn $O(n\log ^2 n)$. Tuy nghe số cạnh có vẻ nhiều nhưng thực thế những thuật toán luồng như Dinic lại chạy rất nhanh nên ta có thể AC bài toán.
**Bonus.** Nếu muốn tối ưu hơn nữa, bạn có thể sử dụng luồng của thầy Lê Minh Hoàng có thể tìm thấy trong notebook của anh RR [tại đây](https://github.com/ngthanhtrung23/ACM_Notebook_new/tree/master/Graph/MaxFlow)
```cpp
void get(int id, int l, int r, int u, int v, int to) {
if (r < u || v < l) return;
if (u <= l && r <= v) {
flow->addEdge(to, id, 1e9);
return;
}
int mid = (l + r) >> 1;
get(id << 1, l, mid, u, v, to);
get(id << 1 | 1, mid + 1, r, u, v, to);
}
void updatePath(int u, int v, int to) {
while (chain[u] != chain[v]) {
if (chain[u] > chain[v]) {
get(1, 1, n, pos[head[chain[u]]], pos[u], to);
u = parent[head[chain[u]]];
} else {
get(1, 1, n, pos[head[chain[v]]], pos[v], to);
v = parent[head[chain[v]]];
}
}
if (pos[u] > pos[v]) swap(u, v);
get(1, 1, n, pos[u], pos[v], to);
}
```
tcmduc
Created at
3 likes