Luồng nghẽn cổ chai cực đại

Buổi 36 — DP on DAG & Profile DP Dynamic Programming
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved