Cycle Free Flow
Xem dạng PDF
Cho một đồ thị liên thông vô hướng có trọng số gồm ~n~ đỉnh và không có chu trình. Với ~q~ cặp đỉnh khác nhau, bạn phải tìm luồng cực đại từ đỉnh đầu tiên tới đỉnh còn lại trong cặp.
Luồng cực đại trong một đồ thị giữa hai đỉnh ~a~ và ~b~ được định nghĩa như sau: Bạn có thể chọn bất kì đường đi nào từ ~a~ tới ~b~ sao cho mỗi cạnh trên đường đi đó đều có một trọng số dương. Sau đó, hãy trừ đi ~1~ đơn vị ở trọng số của mỗi cạnh trên đường đi đó, đồng thời cộng thêm ~1~ vào kết quả. Cứ làm như vậy bao nhiêu lần tùy ý. Giá trị "luồng cực đại" khi đó là kết quả lớn nhất mà bạn có thể đạt được, mỗi bước bạn có thể chọn lại đường đi từ ~a~ đến ~b~ sao cho tối ưu nhất.
Input
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~, là số đỉnh và số cạnh của đồ thị. ~(2 \leq n,m \leq 3*10^5)~
Mỗi dòng trong số ~m~ dòng tiếp theo bao gồm ~3~ số nguyên dương ~u~ ~v~ ~w~, lần lượt là số hiệu hai đỉnh của một cạnh và trọng số ban đầu của cạnh đó. ~(1 \leq w \leq 10^9, u \neq v)~
Dòng tiếp theo chứa số nguyên dương ~q~: số lượng truy vấn mà bạn phải trả lời. ~(1 \leq q \leq 3*10^5)~
Mỗi dòng trong số ~q~ dòng tiếp theo chứa hai số nguyên ~a~ và ~b~, chính là hai đỉnh mà bạn phải tìm luồng cực đại giữa chúng trong truy vấn đó. ~(1 \leq a,b \leq n, a \neq b)~
Dữ liệu đảm bảo đồ thị không có chu trình, khuyên hay cạnh trùng.
Output
- Với mỗi truy vấn, in ra một số nguyên duy nhất là giá trị luồng cực đại giữa hai đỉnh ~a~ và ~b~ trong truy vấn đó.
Sample 1
Input
2 1
1 2 2768
2
1 2
2 1
Output
2768
2768
Sample 2
Input
3 2
3 2 4814
2 1 1832
3
2 1
1 2
3 1
Output
1832
1832
1832
Sample 3
Input
5 4
4 2 10348
1 4 2690
5 4 9807
3 4 8008
5
5 4
1 5
5 4
5 4
1 5
Output
9807
2690
9807
9807
2690
Sample 4
Input
5 4
1 3 2653
4 1 322
5 1 8657
2 4 4896
5
4 2
2 5
2 5
1 3
4 5
Output
4896
322
322
2653
322
Ghi chú
Bạn phải trả lời các truy vấn online. Ban đầu, tác giả định bắt bạn làm như vậy bằng cách mã hóa các dữ liệu đầu vào, nhưng điều này làm cho bài toán khó hơn và khi đọc cảm thấy khó chịu. Vì vậy, hãy tự giác trả lời hết truy vấn thứ nhất, rồi đến truy vấn thứ hai và lần lượt sau đó.
Chúng ta đang luyện tập để ngày một tiến bộ hơn thôi, đúng không ^^
Bình luận
Không biết làm đừng đọc sol nhá <3
bài này giống bài LUBENICA
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.