一般图最大权匹配（General Weighted Matching）

问题描述

给定一个含 $N$ 个顶点、$M$ 条边的简单无向加权图，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，权重为 $w_i$。
求一个最大权匹配——即边集的子集，使得任意两条边不共享顶点，且总权重最大。

输出：

• $X$：匹配的边数（即匹配大小）；
• $W$：匹配的总权重；
• 边列表 $(a_0, b_0), (a_1, b_1), \dots, (a_{X-1}, b_{X-1})$：所选边的端点对。

约束条件

• $1 \leq N \leq 500$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $0 \leq u_i, v_i < N$
• $1 \leq w_i \leq 1\,000\,000$

注：由于 $N \le 500$，可使用带花树的最大权匹配算法（Edmonds’ blossom algorithm for weighted matching）。

输入格式

$N\ M$
$u_0\ v_0\ w_0$
$u_1\ v_1\ w_1$
:
$u_{M-1}\ v_{M-1}\ w_{M-1}$

输出格式

$X\ W$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{X-1}\ b_{X-1}$

7 8
2 0 1
0 5 2
5 6 3
6 1 4
1 0 5
1 3 6
3 4 7
1 4 8

3 15
0 1
3 4
5 6

4 3
0 2 1
1 3 1
1 2 3

1 3
1 2