8213: [yosupo] Graph - General Weighted Matching
[Creator : ]
Description
Given a simple weighted undirected graph with $N$ vertices and $M$ edges. $i$-th edge is $(u_i, v_i)$ with a weight $w_i$.
Calculate the matching in which the sum of weights is maximized.
Calculate the matching in which the sum of weights is maximized.
Input
$N$ $M$
$u_0$ $v_0$ $w_0$
$u_1$ $v_1$ $w_1$
:
$u_{M - 1}$ $v_{M - 1}$ $w_{M-1}$
$u_0$ $v_0$ $w_0$
$u_1$ $v_1$ $w_1$
:
$u_{M - 1}$ $v_{M - 1}$ $w_{M-1}$
Output
$X$ $W$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{X - 1}$ $b_{X - 1}$
$X$ is the size of the maximum matching.
$W$ is the maximum matching weight.
$(a_i, b_i)$ is the edge of the matching.
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{X - 1}$ $b_{X - 1}$
$X$ is the size of the maximum matching.
$W$ is the maximum matching weight.
$(a_i, b_i)$ is the edge of the matching.
Constraints
$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$
$0 \leq M \leq \frac{N(N-1)}{2}$
$0 \leq u_i, v_i < N$
$1 \leq w_i \leq 1\,000\,000$
Sample 1 Input
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
Sample 1 Output
3 15
0 1
3 4
5 6
Sample 2 Input
4 3
0 2 1
1 3 1
1 2 3
Sample 2 Output
1 3
1 2