Hai Luồng Hàng Hóa Song Hành
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một mạng giao thông vô hướng gồm N đỉnh và M cạnh, cạnh thứ i nối u và v có băng thông c (tổng lưu lượng đi qua cạnh theo cả hai chiều không vượt quá c). Có hai loại hàng hóa cần vận chuyển đồng thời:
- Hàng loại 1 từ s_1 đến t_1 với lưu lượng f_1 ≥ 0.
- Hàng loại 2 từ s_2 đến t_2 với lưu lượng f_2 ≥ 0. (Bốn đỉnh s_1, t_1, s_2, t_2 đôi một khác nhau, lưu lượng mỗi loại có thể là số thực không âm).
Hãy tìm giá trị lớn nhất của 2 × (f_1 + f_2).
Dữ liệu vào
- Dòng đầu: hai số nguyên N và M (4 ≤ N ≤ 498, 0 ≤ M ≤ 2500).
- Dòng thứ hai: bốn số nguyên s_1, t_1, s_2, t_2.
- M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, c (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ c ≤ 10^9).
Dữ liệu ra
- Một số nguyên duy nhất: giá trị lớn nhất của 2 × (f_1 + f_2).
Ví dụ
| Input | Output |
|---|---|
| 4 5\n1 3 2 4\n1 2 1\n2 3 1\n3 4 1\n4 1 1\n1 3 1 | 6 |
Giới hạn
- 4 ≤ N ≤ 498
- 0 ≤ M ≤ 2500
- 0 ≤ c ≤ 10^9
Community Discussion