Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKFLOW - Luồng cực đại trên mạng

Trong lý thuyết đồ thị, mạng luồng là một đồ thị có hướng, trong đó mỗi cạnh có một độ thông qua và một giá trị luồng. Lượng luồng trên mỗi cạnh không được vượt quá độ thông qua của cạnh đó. Lượng luồng đi vào một đỉnh phải bằng lượng luồng đi ra khỏi nó, trừ khi đó là đỉnh nguồn (có nhiều lượng luồng đi ra hơn), hay đỉnh đích (có nhiều lượng luồng đi vào hơn). Mạng luồng có thể dùng để mô hình hóa hệ thống đường giao thông, dòng chảy của chất lỏng trong ống, dòng điện trong mạch, hay bất kỳ các bài toán nào tương tự khi có sự di chuyển trong một mạng các nút.

Mô hình các ống dẫn nước bằng một mạng luồng. Mỗi ống nước có đường kính xác định nên chỉ cho phép một lưu lượng nước xác định chảy qua. Ở nơi giao điểm giữa các ống, lưu lượng nước đi vào phải bằng lưu lượng nước đi ra nếu không nước sẽ nhanh chóng bị thất thoát. Ta có một bồn nước, hay đỉnh phát, và một vòi nước, hay đỉnh thu. Một cách trực quan, giá trị luồng trên mạng chính là vận tốc nước chảy ra từ vòi. Luồng còn có thể mô hình sự lưu chuyển của người hay hàng hóa trên các mạng giao thông, dòng điện trong hệ thống phân phối,... Đối với các hệ thống mạng này, luồng đi vào các nút trung gian cần phải bằng luồng đi ra khỏi nút đó. Tính chất này cũng giống như định luật dòng điện Kirchhoff. Mạng luồng còn được ứng dụng trong sinh thái học: mạng luồng xuất hiện khi xem xét sự lưu chuyển chất dinh dưỡng và năng lượng giữa các nhóm khác nhau trong một mạng thức ăn. Các bài toán gắn với loại mạng sinh thái này hoàn toán khác với trường hợp mạng chất lỏng hay mạng giao thông.

Bài toán luồng cực đại trên mạng yêu cầu tìm một luồng tương thích có giá trị lớn nhất trong mạng luồng có một đỉnh phát và một đỉnh thu. Bài toán luồng cực đại trên mạng có thể xem như trường hợp đặc biệt của lớp các bài toán mạng phức tạp hơn, chẳng hạng như bài toán lưu thông. Định lý luồng cực đại-lát cắt hẹp nhất (max-flow min-cut theorem) chỉ ra giá trị luồng cực đại từ s đến t (đỉnh phát đến đỉnh thu) bằng giá trị của lát cắt s-t hẹp nhất trên mạng.

Bạn hãy thử giải quyết bài toán luồng cực đại trên mạng: cho một mạng luồng, hãy tìm giá trị luồng cực đại.

Dữ liệu

  • Dòng đầu tiên chứa 4 số nguyên dương n, m, s, t, (2 ≤ n ≤ 1000) tương ứng là số đỉnh, số cạnh của đồ thị, chỉ số của đỉnh phát và đỉnh thu.
  • m dòng tiếp theo, mỗi dòng có dạng ba số u, v, c cách nhau ít nhất một dấu cách thể hiện có cung u, v trong mạng với khả năng thông qua là c (1 ≤ c ≤ 106).

Kết qủa

In ra một số duy nhất là giá trị của luồng cực đại trên mạng.

Ví dụ

Dữ liệu:
6 8 1 6
1 2 5
1 3 5
2 4 6
2 5 3
3 4 3
3 5 1
4 6 6
5 6 6

Kết qủa
9

Được gửi lên bởi:Duc
Ngày:2008-01-06
Thời gian chạy:0.393s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED

hide comments
2017-07-28 05:42:12
Code Pascal: http://shink.in/5qrFl
Code C: http://shink.in/oBrfL
2017-04-13 16:07:24
biên dịch gặp lỗi là thế bất nào nhể :?
2017-02-27 17:42:03
các cậu ai có code C++ có đọc ghi file input,output bài này cho t xin với. t ko xem được code ở đây.
t đang làm bài tập lớn về thuật toán này. Mong mọi người giúp t, mail t : vanxiu1996@gmail.com
2017-01-02 10:32:13
Lddz AC :))
2016-12-04 05:43:37 Nguyễn Hữu Phong
preflow push 90.91 thì lấy lát cắt đi vào t, chứ không phải lát cắt đi ra từ s~~!@
2016-11-20 12:00:08
vì đây là bài cơ bản :p nên Ford-Fulkerson thôi !
2016-11-17 09:30:35 le tuan dung
xin chao 11 tin
2016-11-07 11:51:49
AC một nốt nhạc
2016-10-14 16:41:59
tại sao bài này ford fulkerson AC vậy
2016-07-21 10:25:17 xin đừng quên tôi
Tham khảo thuật toán và code: http://yeulaptrinh.pw/295/nkflow-spoj/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.