P5632 [Template] Stoer-Wagner

Define the minimum cut of an undirected graph $G$ as follows: it is a set of edges such that removing these edges can make $G$ split into two connected components, and the sum of edge weights in this set is minimal. Given an undirected graph $G$, find its minimum cut.

The first line contains two numbers $n, m$, representing the number of vertices and the number of edges. The next $m$ lines each contain three positive integers $a_i, b_i, w_i$, indicating that there is an edge between $a_i$ and $b_i$ with weight $w_i$.

Output one line with one integer representing the minimum cut of $G$. If the graph is disconnected, output `0`.

For the first $20\%$ of the testdata, $n \leq 10$. For the first $40\%$ of the testdata, $n \leq 100$. For another $10\%$ of the testdata, the input is guaranteed to be a tree. For another $10\%$ of the testdata, the input is guaranteed to be a chain. For $100\%$ of the testdata, $n \leq 600, m \leq \frac{n\times (n-1)}{2}$, and it is guaranteed that $\sum_{i=1}^{m} w_i \leq 10^9$. #### PS: If you want to submit “maximum flow / minimum cut tree”, just forget it. Translated by ChatGPT 5