Global minimum cut

Write codeHard45 min

Your task

Given an undirected weighted graph on n nodes (n >= 2) as edges [u, v, w] with positive integer weights (parallel edges allowed, their weights add), find the global minimum cut: partition the nodes into two non-empty groups so that the total weight of edges crossing the partition is minimized, over all possible partitions (there is no fixed source or sink). Return that minimum crossing weight. A disconnected graph has a cut of 0. Constraints: 2 <= n <= 60.

Examples

global_min_cut(n: int, edges: list[list[int]]) -> int

Example 1

Inputglobal_min_cut(4, [[0, 1, 3], [1, 2, 1], [2, 3, 3], [0, 3, 1], [1, 3, 2]])

Output4