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

MINCOST - Luồng với chi phí nhỏ nhất

Cho một mạng đối xứng có n đỉnh, mỗi cạnh của mạng có một khả năng thông qua và một cước phí vận chuyển nhất định (như nhau theo cả hai chiều). Cho trước một lượng hàng S cần vận chuyển từ đỉnh nguồn (đánh số là s) tới đỉnh đích (đánh số là f). Hãy tìm một phương án vận chuyển, nghĩa là hãy xác định trên mỗi cạnh của mạng cần vận chuyển bao nhiêu hàng, theo chiều nào, sao cho phù hợp với khả năng thông qua của mạng (trên mỗi cạnh lượng hàng vận chuyển không vượt quá khả năng thông qua của cạnh) và vận chuyển được lượng hàng S từ nguồn về đích với tổng chi phí vận chuyển là nhỏ nhất.
Về mặt toán học, bài toán tìm luồng với chi phí nhỏ nhất có thể diễn đạt như sau:

Cực tiểu hóa hàm chi phí ∑cijxij với điều kiện:

  1. ∑(xij - xji) với j = 1..n, có giá trị
    • S nếu i = s
    • 0 nếu i ≠ s; i ≠ n
    • -S nếu i = f
  2. 0 ≤ xij ≤ dij với mọi cạnh (i, j)

Ở đây đỉnh nguồn được đánh số là s, đỉnh đích là f, cij là chi phí vận chuyển một đơn vị hàng trên cạnh (i, j), dij là khả năng thông qua của cạnh (i, j); còn xij là khối lượng hàng vận chuyển trên cạnh (i, j) cần xác định.

Input

  • Dòng đầu là n, m, k, s, f : Số đỉnh, số đường, số đơn vị hàng cần vận chuyển. đỉnh bắt đầu, đỉnh kết thúc
  • m dòng tiếp theo mỗi bao gồm u, v, c, d cho biết có đường từ u -> v, v -> u với chi phí là c và khả năng thông qua là d.

Output

  • Dòng đầu, nếu không vận chuyển được ghi –1, nếu có ghi tổng chi phí vận chuyển.
  • Nếu có nghiệm thì một số dòng tiếp ghi u, v, i cho biết vận chuyển i đơn vị hàng từ trên cạnh u -> v. Kết thúc bằng "0 0 0".

Example


Input:
6 8 5 1 6
1 2 1 2
1 4 3 4
2 3 1 4
2 5 5 2
3 4 2 4
3 6 1 2
4 6 4 1
5 6 6 2

Output:
43
1 2 2
1 4 3
2 5 2
3 6 2
4 3 2
4 6 1
5 6 2
0 0 0

Giới hạn:
  • n <= 100
  • dij <= 30000
  • cij <= 109
Phạm vi tính toán là Longint.

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-09-15
Thời gian chạy:1.359s
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 VB.NET

hide comments
2016-03-20 15:26:09
Ko vận chuyển đc nghĩa là không vận chuyển hết hay sao z??
2014-12-26 15:51:32 Ðức Anh
Hình như bài này giới hạn n sai, ban đầu mình để maxN = 110 bị SIGABRT, sửa maxN thành 210 AC luôn.
2014-09-05 15:26:06 Thcs Ðặng Chánh Kỷ
phê lòi với bài này , code như ngu, đoạn lấy delta phải lấy min với k rồi trừ mới được, bài này cạnh lặp vẫn không ảnh hưởng tới kết quả bài toán
2014-08-07 08:12:14 ■■‡[ND] Bee Sociu■■‡
Luong co ban ! 1 tat AC
2013-10-18 14:26:00 RR
Bài này test sai. Trong input cạnh (u, v) xuất hiện nhiều lần nhưng phải dùng duy nhất cạnh (u, v) xuất hiện cuối cùng thì mới acc
2013-06-30 13:24:46
bai nay canh bi lap a?
2013-03-13 20:47:09 Nguyên
Bài cơ bản như vậy cũng để test sai.
2010-10-22 22:55:06 caibut
kho ghe
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.