4
Ich muss einen linearen Algorithmus (O (| V | + | E |) finden, der den maximalen Durchfluss in einem Diagramm findet, wo der ursprüngliche maximale Durchfluss bekannt ist, aber die Kapazität von jede Kante wird von 1.Änderung des maximalen Durchflusses, wenn jede Flankenkapazität erhöht wird
ich glaube nicht, dass funktioniert. Sie haben vielleicht mehrere Min-Schnitte, mit einer anderen Anzahl von Kanten, die sich kreuzen.Wenn Sie eine mit mehr Kanten wählen, wird der Fluss immer noch die Kapazität des anderen Min-Schnitts übersteigen. – user1255841