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.|

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

Cho mạng G = (V, E, c, s, t) với G = (V, E) là một đồ thị có hướng, không khuyên, có n đỉnh và m cung. Hai đỉnh s, t phân biệt lần lượt là đỉnh phát và đỉnh thu. Khả năng thông qua của cung (u, v) là c(u, v). Từ s chỉ có cung đi ra và từ t chỉ có cung đi vào. hãy tìm một luồng cực đại trêng mạng đã cho.

Dữ liệu vào:

  • Dòng đầu chứa bốn số nguyên n, m, s, t là số đỉnh và số cung của G, đỉnh phát và đỉnh thu.
  • m dòng tiếp theo, mỗi dòng chứa ba số số u, v, c cho biết một cạnh nối hai đỉnh u và v trong G và khả năng thông qua c = w(u, v) tương ứng.

Dữ liệu ra:

  • Dòng đầu ghi một số nguyên là giá trị của luồng.
  • những dong tiếp theo, mỗi dòng ghi ba số nguyên dương u, v, f với (u, v) là một cung và f là giá trị của luồng trên cung đó (chỉ liệt kê những cung (u, v) có f(u, v) > 0).

Ví dụ:

Dữ liệu vào:
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
Dữ liệu ra:
9
1 2 5
1 3 4
2 4 3
2 5 2
3 4 3
3 5 1
4 6 6
5 6 3

Giới hạn: 1 ≤ n ≤ 1000; m ≤ 105; 1 ≤ c ≤ 10000. 


Được gửi lên bởi:noname00.pas
Ngày:2017-10-31
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.