Jaringan aliran adalah grafik terarah G = (V, E)
dengan simpul sumber s ϵ V
dan simpul wastafel t ϵ V
, dan di mana setiap sisi (u, v) ϵ E
pada grafik (menghubungkan simpul u ϵ V
dan v ϵ V
) memiliki 2 jumlah yang terkait dengannya:
c(u, v) >= 0
, kapasitas tepia(u, v) >= 0
, biaya pengiriman satu unit melalui tepi
Kami mendefinisikan suatu fungsi 0 <= f(u, v) <= c(u, v)
menjadi jumlah unit yang dilewatkan melalui tepi yang diberikan (u, v)
. Dengan demikian, biaya untuk keunggulan yang diberikan (u, v)
adalah a(u, v) * f(u, v)
. Masalah aliran biaya minimum didefinisikan sebagai meminimalkan total biaya pada semua sisi untuk jumlah aliran d
tertentu, yang diberikan oleh kuantitas berikut:
Batasan berikut berlaku untuk masalah:
- Persyaratan kapasitas : aliran melalui tepi tertentu mungkin tidak melebihi kapasitas tepi itu (
f(u, v) <= c(u, v)
). - Simetri miring : aliran melalui tepi yang diberikan harus antisimetris ketika arahnya terbalik (
f(u, v) = -f(v, u)
). - Konservasi aliran : aliran bersih ke simpul non-sumber non-wastafel harus 0 (untuk masing-masing
u ∉ {s, t}
, menjumlahkan semuaw
,sum f(u, w) = 0
). - Diperlukan aliran : aliran bersih dari sumber dan aliran bersih ke wastafel harus sama dengan aliran yang diperlukan melalui jaringan (menjumlahkan semua
u
,sum f(s, u) = sum f(u, t) = d
).
Diberikan jaringan aliran G
dan aliran yang diperlukan d
, mengeluarkan biaya minimum untuk mengirim d
unit melalui jaringan. Anda dapat mengasumsikan bahwa ada solusi. d
dan semua kapasitas dan biaya adalah bilangan bulat non-negatif. Untuk jaringan dengan N
simpul berlabel [0, N-1]
, simpul sumber akan menjadi 0
dan simpul wastafel akan N-1
.
Ini adalah kode-golf , jadi jawaban tersingkat (dalam byte) menang. Ingatlah bahwa ini adalah kompetisi dalam bahasa dan juga antar bahasa, jadi jangan takut untuk mengirim solusi dalam bahasa verbal.
Built-in diizinkan, tetapi Anda disarankan untuk memasukkan solusi tanpa builtin, baik sebagai solusi tambahan dalam jawaban yang sama, atau sebagai jawaban independen.
Input mungkin dengan cara yang masuk akal yang mencakup kapasitas dan biaya masing-masing sisi dan permintaan.
Uji Kasus
Test case disediakan dalam format berikut:
c=<2D matrix of capacities> a=<2D matrix of costs> d=<demand> -> <solution>
c=[[0, 3, 2, 3, 2], [3, 0, 5, 3, 3], [2, 5, 0, 4, 5], [3, 3, 4, 0, 4], [2, 3, 5, 4, 0]] a=[[0, 1, 1, 2, 1], [1, 0, 1, 2, 3], [1, 1, 0, 2, 2], [2, 2, 2, 0, 3], [1, 3, 2, 3, 0]] d=7 -> 20
c=[[0, 1, 1, 5, 4], [1, 0, 2, 4, 2], [1, 2, 0, 1, 1], [5, 4, 1, 0, 3], [4, 2, 1, 3, 0]] a=[[0, 1, 1, 2, 2], [1, 0, 2, 4, 1], [1, 2, 0, 1, 1], [2, 4, 1, 0, 3], [2, 1, 1, 3, 0]] d=7 -> 17
c=[[0, 1, 4, 5, 4, 2, 3], [1, 0, 5, 4, 3, 3, 5], [4, 5, 0, 1, 5, 5, 5], [5, 4, 1, 0, 3, 2, 5], [4, 3, 5, 3, 0, 4, 4], [2, 3, 5, 2, 4, 0, 2], [3, 5, 5, 5, 4, 2, 0]] a=[[0, 1, 4, 2, 4, 1, 1], [1, 0, 3, 2, 2, 1, 1], [4, 3, 0, 1, 4, 5, 2], [2, 2, 1, 0, 2, 2, 3], [4, 2, 4, 2, 0, 4, 1], [1, 1, 5, 2, 4, 0, 2], [1, 1, 2, 3, 1, 2, 0]] d=10 -> 31
c=[[0, 16, 14, 10, 14, 11, 10, 4, 3, 16], [16, 0, 18, 19, 1, 6, 10, 19, 5, 4], [14, 18, 0, 2, 15, 9, 3, 14, 20, 13], [10, 19, 2, 0, 2, 10, 12, 17, 19, 22], [14, 1, 15, 2, 0, 11, 23, 25, 10, 19], [11, 6, 9, 10, 11, 0, 14, 16, 25, 4], [10, 10, 3, 12, 23, 14, 0, 11, 7, 8], [4, 19, 14, 17, 25, 16, 11, 0, 14, 5], [3, 5, 20, 19, 10, 25, 7, 14, 0, 22], [16, 4, 13, 22, 19, 4, 8, 5, 22, 0]] a=[[0, 12, 4, 2, 9, 1, 1, 3, 1, 6], [12, 0, 12, 16, 1, 2, 9, 13, 2, 3], [4, 12, 0, 2, 2, 2, 2, 10, 1, 1], [2, 16, 2, 0, 2, 1, 8, 4, 4, 2], [9, 1, 2, 2, 0, 5, 6, 23, 5, 8], [1, 2, 2, 1, 5, 0, 13, 12, 12, 1], [1, 9, 2, 8, 6, 13, 0, 9, 4, 4], [3, 13, 10, 4, 23, 12, 9, 0, 13, 1], [1, 2, 1, 4, 5, 12, 4, 13, 0, 13], [6, 3, 1, 2, 8, 1, 4, 1, 13, 0]] d=50 -> 213
Kasus uji ini dihitung dengan pustaka NetworkX Python .
Jawaban:
[R + lpSolve ],
201186149144 byteCobalah online!
Kode ini membangun Masalah Linear berikut dan menyelesaikannya menggunakan
lpSolve
paket:x -> y
x -> y
x -> y
sumber
lpSolve
... :(Bahasa Wolfram, 42 byte
Builtin sepele. Solusi non-builtin segera hadir.
sumber
Python 3 + NetworkX , 137 byte
Tidak ada tautan TryItOnline karena TIO tidak memiliki pustaka NetworkX yang diinstal
Mengambil input grafik sebagai daftar tepi dengan atribut kapasitas dan berat, seperti ini:
Ini adalah versi golf dari kode yang saya gunakan untuk memverifikasi kasus uji.
sumber