P4123 [CQOI2016] Distinct Minimum Cuts

Students who have studied graph theory all know the concept of the minimum cut: For a graph, a partition of the nodes divides all nodes into two parts. If nodes $s, t$ are not in the same part, then the partition is called a cut with respect to $s, t$. For a weighted graph, the capacity of a cut is defined as the sum of the weights of edges whose endpoints lie in different parts, and the $s, t$ minimum cut is the cut of minimum capacity among all cuts with respect to $s, t$. For contestants preparing for the NOI, finding the minimum cut between two nodes in a weighted graph is no longer difficult. Let us broaden the view: In an undirected connected graph with $N$ nodes, consider the minimum cut capacity for every unordered pair of nodes. In total we obtain $\,$ $N(N-1)/2$ $\,$ values. How many of these values are distinct? This seems like an interesting problem.

The first line contains two integers $N, M$, the number of nodes and the number of edges. Each of the next $M$ lines contains three integers $u, v, w$, indicating there is an edge between node $u$ and node $v$ (indexed from $1$) with weight $w$.

Output a single integer on the first line, the number of distinct minimum cut capacities.

Constraints: $1 \leq N \leq 850$, $1 \leq M \leq 8500$, $1 \leq w \leq 100000$. Translated by ChatGPT 5