QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 512 MB Hackable ✓
[0]

# 900. 一般图最大权匹配

Statistics

Source: Library Checker

Statement

Given a simple weighted undirected graph with N vertices and M edges. i-th edge is (ui,vi) with a weight wi. Calculate the matching in which the sum of weights is maximized.

N 頂点 M 辺からなる単純重み付き無向グラフが与えられます。i 番目の辺は (ui,vi) を結ぶ重み wi の辺です。 重みの総和が最大であるようなマッチングをひとつ求めてください。

Constraint

  • 1N500
  • 0MN(N1)2
  • 0ui,vi<N
  • 1wi1000000

Input

  • N M
  • u0 v0 w0
  • u1 v1 w1
  • :
  • uM1 vM1 wM1

Output

  • X W
  • a0 b0
  • a1 b1
  • :
  • aX1 bX1

X is the size of the maximum matching. W is the maximum matching weight. (ai,bi) is the edge of the matching.

X はマッチングの辺の個数、W はマッチングの重みの総和、(ai,bi) はマッチングの辺です。

Example

Input 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

Output 1

3 15
0 1
3 4
5 6

Input 2

4 3
0 2 1
1 3 1
1 2 3

Output 2

1 3
1 2