#P1321. Sgu206 Road

    ID: 333 传统题 1000ms 512MiB 尝试: 72 已通过: 9 难度: 9 上传者: 标签>CF2700省选/NOI-二分图建模线性规划对偶建模带权二分图匹配增广路支配关系异或抵消位集求交枚举置位位置最优性剪枝

Sgu206 Road

题目描述

给你一个 NN 个点 MM 条边的图( M≥N−1M \geq N - 1),每条边有个权值 CiC_i,前面 N–1N – 1 条边构成一颗树,现在你需要给每条边构造一个整数新权值 DiD_i,使得前 N–1N–1 条边构成的生成树是该图的最小生成树,并且使

∑i=1M∣Di−Ci∣\sum^M_{i=1}|D_i-C_i|

最小。允许前 N−1N-1 条边构成的树与其他生成树并列最优。

输入格式

第一行两个数 N,MN, M。 接下来M行每行三个数 ai,bi,cia_i,b_i,c_i,表示一条边,保证无重边无自环,1≤Ci≤100001\le C_i\le10000。

输出格式

仅一行,表示最小花费。

4 5 
4 1 7 
2 1 5 
3 4 4 
4 2 5 
1 3 1
6

提示

30%的数据,N≤60,M≤400N\leq60, M \leq400。

100%的数据,N≤1000,M≤10000N\leq1000, M\leq 10000。