Luồng nghẽn cổ chai cực đại
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh và $M$ cạnh có hướng, mỗi cạnh có thông lượng $c > 0$. Cho tập hợp $S$ gồm $K_S$ đỉnh nguồn và tập hợp $T$ gồm $K_T$ đỉnh đích (hai tập $S$ và $T$ rời nhau). Tìm thông lượng lớn nhất của một đường đi từ một đỉnh bất kỳ thuộc $S$ đến một đỉnh bất kỳ thuộc $T$, trong đó thông lượng của một đường đi là giá trị nhỏ nhất của các cạnh trên đường đi đó. Nếu không có đường đi nào, in ra 0.
Dữ liệu vào
- Dòng đầu chứa 4 số nguyên $N, M, K_S, K_T$.
- Dòng thứ hai chứa $K_S$ số nguyên là các đỉnh trong $S$.
- Dòng thứ ba chứa $K_T$ số nguyên là các đỉnh trong $T$.
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, c$.
Dữ liệu ra
- In ra thông lượng lớn nhất tìm được (hoặc
0).
Ví dụ
| Input | Output |
|---|---|
| 5 5 2 2\n1 2\n4 5\n1 3 10\n2 3 7\n3 4 5\n3 5 8\n1 4 4 | 8 |
Giới hạn
- $2 \le N \le 10^5$
- $0 \le M \le 2 \cdot 10^5$
- $1 \le c \le 10^9$
Community Discussion