Skip to content

minCostMaxFlow ​

minCostMaxFlow(edges, vertexCount, source, sink) augments residual paths with costs and returns total flow and total cost.

SignatureReturnsComplexity
minCostMaxFlow(edges: [usize, usize, i32, i32][], vertexCount: usize, source: usize, sink: usize)[i32, i32]O(FVE)
tyrus
import { minCostMaxFlow } from "tyrus:algorithm";

const result: [i32, i32] = minCostMaxFlow([[0, 1, 2, 3]], 2, 0, 1);
print(result[0], result[1]); // 2 6

Study result ​

tyrus
interface MinCostMaxFlowInfo { maxFlow: i32; minimumCost: i32; augmentationCount: usize; costRelaxationCount: usize; cumulativeCosts: i32[]; }
tyrus
import { MinCostMaxFlowInfo, minCostMaxFlowInfo } from "tyrus:algorithm";
const info: MinCostMaxFlowInfo = minCostMaxFlowInfo([[0, 1, 2, 1], [0, 2, 1, 2], [1, 2, 1, 1], [1, 3, 1, 3], [2, 3, 2, 1]], 4, 0, 3);
print(info.maxFlow); // 3
print(info.minimumCost); // 10
print(info.augmentationCount); // 5
print(info.costRelaxationCount); // 20
print(info.cumulativeCosts); // [10]