Hai Luồng Hàng Hóa Song Hành

Buổi 47 — Luồng cực đại (Dinic)
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved