search

jensharder91 / -Lab-Efficient-Algorithms

0 stars 0 forks source link

Blatt 05 Aufgabe 2 #31

Open jensharder91 opened 6 years ago

P4nd4b43r commented 6 years ago

Für die Aufgabe "EdgeOrientation" liefert der folgende Testfall einen Fehler: 10 9 1 2 3 4 5 6 7 8 7 9 7 10 8 9 8 10 9 10 Eure Lösung lautet "3", es ist aber ein maximaler Eingangsgrad von "2" möglich.

jensharder91 commented 6 years ago

Hast du eine Idee, wie man das als Flussproblem machen könnte? Hab viel Zeit investiert, aber irgendwie klappts nicht so wie ich will..

Source geht zu jedem Knoten und jeder Knoten hat eine Kante zu Senke. Man könnte die Kante zur Senke immer incrementieren jede Runde, bis man den Fluss nicht mehr erhöhen kann.

Da gibt es aber noch ein paar Probleme. Vielleicht hast du noch eine Idee?