Masalah aliran biaya minimum

9

Jaringan aliran adalah grafik terarah G = (V, E)dengan simpul sumber s ϵ Vdan simpul wastafel t ϵ V, dan di mana setiap sisi (u, v) ϵ Epada grafik (menghubungkan simpul u ϵ Vdan v ϵ V) memiliki 2 jumlah yang terkait dengannya:

  1. c(u, v) >= 0, kapasitas tepi
  2. a(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 dtertentu, yang diberikan oleh kuantitas berikut:

biaya

Batasan berikut berlaku untuk masalah:

  1. Persyaratan kapasitas : aliran melalui tepi tertentu mungkin tidak melebihi kapasitas tepi itu ( f(u, v) <= c(u, v)).
  2. Simetri miring : aliran melalui tepi yang diberikan harus antisimetris ketika arahnya terbalik ( f(u, v) = -f(v, u)).
  3. Konservasi aliran : aliran bersih ke simpul non-sumber non-wastafel harus 0 (untuk masing-masing u ∉ {s, t}, menjumlahkan semua w, sum f(u, w) = 0).
  4. 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 Gdan aliran yang diperlukan d, mengeluarkan biaya minimum untuk mengirim dunit melalui jaringan. Anda dapat mengasumsikan bahwa ada solusi. ddan semua kapasitas dan biaya adalah bilangan bulat non-negatif. Untuk jaringan dengan Nsimpul berlabel [0, N-1], simpul sumber akan menjadi 0dan simpul wastafel akan N-1.

Ini adalah , 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 .

Mego
sumber
Sandbox
Mego
1
Bermain

Jawaban:

3

[R + lpSolve ], 201 186 149 144 byte

function(c,a,d,`^`=rep,N=ncol(c),G=diag(N),P=t(1^N),M=P%x%G+G%x%-P)lpSolve::lp(,a,rbind(M,diag(N*N)),c('=','<')^c(N,N*N),c(d,0^(N-2),-d,c))$objv

Cobalah online!

Kode ini membangun Masalah Linear berikut dan menyelesaikannya menggunakan lpSolvepaket:

msayanxV yVSEBUAHx,yfx,yskamubject tHai:xVfv,x-fx,v=0vV:v{s,t}xVfs,x-fx,s=dxVft,x-fx,t=-dfx,bCx,bxV,yV

  • V
  • s
  • t
  • SEBUAHx,yx -> y
  • fx,yx -> y
  • dts
  • Cx,yx -> y
menggali semua
sumber
Bagus, pemrograman linier :) Sayangnya sebagian besar bahasa tidak memiliki lpSolve... :(
Quintec
Sayangnya itu benar ... BTW itu tidak tersedia pada basis-R, ini paket ... Saya harus meminta untuk menginstal di TIO;)
digEmAll
Untuk beberapa alasan saya belum menemukan cara singkat untuk memodifikasi MinCostMaxFlow menjadi MinCostFlow ... otak saya digoreng lol, saya berharap ada fungsi untuk ini dalam bahasa selain Mathematica
Quintec
@Quintec: apakah Anda merujuk pada implementasi spesifik (misalnya dalam bahasa tertentu) MinCostMaxFlow?
digEmAll
Tidak, algoritma kode tangan saya
Quintec
1

Bahasa Wolfram, 42 byte

FindMinimumCostFlow[#,1,VertexCount@#,#2]&

Builtin sepele. Solusi non-builtin segera hadir.

lirtosiast
sumber
Apakah akan datang dalam 6-8 minggu? : P
Quintec
1

Python 3 + NetworkX , 137 byte

from networkx import*
def f(g,d,z='demand'):N=len(g)**.5//1;G=DiGraph(g);G.node[0][z]=-d;G.node[N-1][z]=d;return min_cost_flow_cost(G)

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:

[(0, 0, {'capacity': 0, 'weight': 0}), (0, 1, {'capacity': 3, 'weight': 1}), (0, 2, {'capacity': 2, 'weight': 1}), (0, 3, {'capacity': 3, 'weight': 2}), (0, 4, {'capacity': 2, 'weight': 1}), (1, 0, {'capacity': 3, 'weight': 1}), (1, 1, {'capacity': 0, 'weight': 0}), (1, 2, {'capacity': 5, 'weight': 1}), (1, 3, {'capacity': 3, 'weight': 2}), (1, 4, {'capacity': 3, 'weight': 3}), (2, 0, {'capacity': 2, 'weight': 1}), (2, 1, {'capacity': 5, 'weight': 1}), (2, 2, {'capacity': 0, 'weight': 0}), (2, 3, {'capacity': 4, 'weight': 2}), (2, 4, {'capacity': 5, 'weight': 2}), (3, 0, {'capacity': 3, 'weight': 2}), (3, 1, {'capacity': 3, 'weight': 2}), (3, 2, {'capacity': 4, 'weight': 2}), (3, 3, {'capacity': 0, 'weight': 0}), (3, 4, {'capacity': 4, 'weight': 3}), (4, 0, {'capacity': 2, 'weight': 1}), (4, 1, {'capacity': 3, 'weight': 3}), (4, 2, {'capacity': 5, 'weight': 2}), (4, 3, {'capacity': 4, 'weight': 3}), (4, 4, {'capacity': 0, 'weight': 0})]

Ini adalah versi golf dari kode yang saya gunakan untuk memverifikasi kasus uji.

Mego
sumber