Skip to content

minCut ​

minCut(capacity, source, sink) calcula un flujo máximo y devuelve su valor y las aristas de capacidad que cruzan el corte mínimo correspondiente.

FirmaRetornoComplejidad
minCut(capacity: i32[][], source: usize, sink: usize)[i32, [usize, usize][]]O(V²E)
tyrus
import { minCut } from "tyrus:algorithm";

const result: [i32, [usize, usize][]] = minCut([[0, 2], [0, 0]], 0, 1);
print(result[0], result[1].length); // 2 1

Resultado de estudio ​

tyrus
interface MinCutInfo { cutValue: i32; sourcePartition: usize[]; sinkPartition: usize[]; cutEdges: [usize, usize][]; flowEdges: [usize, usize, i32][]; }
tyrus
import { MinCutInfo, minCutInfo } from "tyrus:algorithm";
const info: MinCutInfo = minCutInfo([[0, 3, 2, 0], [0, 0, 1, 2], [0, 0, 0, 3], [0, 0, 0, 0]], 0, 3);
print(info.cutValue); // 5
print(info.sourcePartition); // [0]
print(info.sinkPartition); // [1, 2, 3]
print(info.cutEdges); // [[0, 1], [0, 2]]
print(info.flowEdges); // [[0, 1, 3], [0, 2, 2], [1, 2, 1], [1, 3, 2], [2, 3, 3]]