Ein Flussnetzwerk ist ein gerichteter Graph G = (V, E)
mit einem Quell- s ϵ V
und einem Senkenscheitelpunkt t ϵ V
, mit denen jeder Kante (u, v) ϵ E
des Graphen (Verbindungsknoten u ϵ V
und v ϵ V
) zwei Größen zugeordnet sind:
c(u, v) >= 0
, die Kapazität der Kantea(u, v) >= 0
, die Kosten für das Senden einer Einheit durch die Kante
Wir definieren eine Funktion 0 <= f(u, v) <= c(u, v)
als die Anzahl der Einheiten, die durch eine bestimmte Kante geleitet werden (u, v)
. Somit sind die Kosten für eine bestimmte Kante (u, v)
liegt a(u, v) * f(u, v)
. Das Problem des Mindestkostenflusses ist definiert als Minimierung der Gesamtkosten über alle Kanten für eine bestimmte Durchflussmenge d
, gegeben durch die folgende Menge:
Die folgenden Einschränkungen gelten für das Problem:
- Kapazitätsanforderungen : Der Durchfluss durch eine bestimmte Kante darf die Kapazität dieser Kante nicht überschreiten (
f(u, v) <= c(u, v)
). - Schrägsymmetrie : Die Strömung durch eine bestimmte Kante muss antisymmetrisch sein, wenn die Richtung umgekehrt wird (
f(u, v) = -f(v, u)
). - Flusserhaltung : der Nettofluss in jeden nicht-Senke nicht-Quellknoten muss 0 sein (für jeden
u ∉ {s, t}
, über alle Summierenw
,sum f(u, w) = 0
). - Erforderliche Strömungs : das Netz von der Quelle ausfließen und dem Nettostrom in die Spüle beide müssen den erforderlichen Durchfluss durch das Netz equal (Summation über alle
u
,sum f(s, u) = sum f(u, t) = d
).
Geben Sie bei einem Flow-Netzwerk G
und einem erforderlichen Flow d
die Mindestkosten für das Senden von d
Einheiten über das Netzwerk aus. Sie können davon ausgehen, dass eine Lösung vorhanden ist. d
Alle Kapazitäten und Kosten sind nicht negative ganze Zahlen. Bei einem Netzwerk mit mit N
gekennzeichneten [0, N-1]
Scheitelpunkten ist der Quellscheitelpunkt 0
und der Senkenscheitelpunkt N-1
.
Dies ist Code-Golf , daher gewinnt die kürzeste Antwort (in Bytes). Denken Sie daran, dass dies ein Wettbewerb innerhalb von Sprachen sowie zwischen Sprachen ist. Haben Sie also keine Angst, eine Lösung in einer ausführlichen Sprache zu veröffentlichen.
Eingebaute sind zulässig, es wird jedoch empfohlen, Lösungen ohne eingebaute Elemente entweder als zusätzliche Lösung in dieselbe Antwort oder als unabhängige Antwort aufzunehmen.
Die Eingabe kann auf jede vernünftige Weise erfolgen, die die Kapazitäten und Kosten jeder Kante und die Nachfrage umfasst.
Testfälle
Testfälle werden im folgenden Format bereitgestellt:
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
Diese Testfälle wurden mit der NetworkX Python-Bibliothek berechnet .
Antworten:
[R + lpSolve ],
201186149144 BytesProbieren Sie es online aus!
Der Code erstellt das folgende lineare Problem und löst es mit dem
lpSolve
Paket:x -> y
x -> y
x -> y
quelle
lpSolve
... :(Wolfram Language, 42 Bytes
Trivial eingebaut. Nicht eingebaute Lösung kommt bald.
quelle
Python 3 + NetworkX , 137 Bytes
Kein TryItOnline-Link, da in TIO die NetworkX-Bibliothek nicht installiert ist
Nimmt die Grafikeingabe als Kantenliste mit Kapazitäts- und Gewichtsattributen wie folgt:
Dies ist eine Golfversion des Codes, mit dem ich die Testfälle überprüft habe.
quelle