#80. 二分图最大权匹配

题目描述

从前一个和谐的班级，有 $n_b$ 个男生，有 $n_g$ 个女生。编号分别为 $1, 2, \dots, n_b$ 和 $1, 2, \dots, n_g$。

有若干个这样的条件：第 $v$ 个男生和第 $u$ 个女生愿意结为配偶，且结为配偶后幸福程度为 $w$。

请问这个班级里幸福程度之和最大是多少？

输入格式

第一行三个正整数 $n_b, n_g, m$。

接下来 $m$ 行，每行三个整数 $v, u, w$，表示第 $v$ 个男生和第 $u$ 个女生愿意结为配偶，且幸福程度为 $w$。
保证 $1 \le v \le n_b$，$1 \le u \le n_g$，且同一对 $(v, u)$ 不会重复出现。

输出格式

第一行一个整数，表示幸福程度之和的最大值。

接下来一行 $n_b$ 个整数，描述一组最优方案：第 $v$ 个整数表示 $v$ 号男生的配偶编号。

• 若 $v$ 号男生没配偶，请输出 0。

样例一

input

2 2 3
1 1 100
1 2 1
2 1 1

output

100
1 0

解释：

• 男生 与女生 1 配对，幸福值 100；
• 男生 2 未匹配 → 输出 0；
• 总幸福值最大为 100

限制与约定

• $1 \le n_b, n_g \le 400$
• $1 \le m \le 160\,000$
• $1 \le w \le 10^9$
• 时间限制：$1\,\text{s}$
• 空间限制：$256\,\text{MB}$