9489 - 二分图最大权匹配
时间限制 : 1 秒
内存限制 : 128 MB
给定一张二分图，左右部均有 n 个点，共有 m 条带权边，且保证有完美匹配。
求一种完美匹配的方案，使得最终匹配边的边权之和最大。
输入
第一行两个整数 n,m，含义见题目描述。
第 2\sim m+1 行，每行三个整数 y,c,h 描述了图中的一条从左部的 y 号结点到右部的 c 号节点，边权为 h 的边。
输出
本题存在 Special Judge。
第一行一个整数 ans 表示答案。
第二行共 n 个整数 a_1,a_2,a_3\cdots a_n，其中 a_i 表示完美匹配下与右部第 i 个点相匹配的左部点的编号。如果存在多种方案，请输出任意一种。
样例
输入
5 7 5 1 600 4 2 587 1 3 635 3 4 559 2 5 626 1 2 -297 4 5 -732
输出
3007 5 4 1 3 2
提示
- 对于 100\% 的数据，满足 1\leq n\leq 500，1\leq m\leq n^2， |h |\leq 10^4 。保证没有重边。
来源
模板