P6699 [Template] Maximum Weight Matching in a General Graph

This is a template problem, with no background.

Given an undirected weighted graph with $n$ vertices and $m$ weighted edges. Find a matching such that the sum of the weights of the matched edges is maximized.

The first line contains two numbers, $n$ and $m$. The next $m$ lines each contain three numbers: $u$, $v$, $w$, indicating that there is an edge between vertex $u$ and vertex $v$ with weight $w$.

The first line contains one number: the maximum total edge weight. The next line contains $n$ integers, describing one optimal solution. The $v$-th integer is the index of the vertex matched with vertex $v$. If vertex $v$ is not matched, output 0.

Constraints: $1 \le n \le 400$, $1 \le m \le 79800$, $1 \le w \le 5\times10^8$. Translated by ChatGPT 5