AT_joisc2015_k.遺産相続

JOISC2015 Day4T1 遗产继承

给定一个$N$个点、$M$条边的无向图，每条边有权值，任意两条边的权值不同。图上保证没有自环，但是可能有重边。每条边有一个标记值，初始每条边的标记值均为$0$。

接下来对这个图进行$K$次操作，第$i$次操作时执行如下操作：在图中选择一个边的集合，满足：

1、其包含的所有边的标记值都是$0$；

2、不存在任何非空子集满足这个子集在图上构成环；

3、选择的集合中所有边的权值之和是当前所有可能的选择方案中权值和最大的选择方案；

然后将这些边的标记值赋为$i$。

求$K$次操作完成之后每一条边的标记值。

第一行三个正整数$N,M,K$，意义如上所述；

接下来$M$行每行三个正整数$A_i,B_i,C_i$表示一条连接$(A_i,B_i)$、权值为$C_i$的边。

$M$行每行一个非负整数表示输入的第$i$条边在操作完成之后的标记值。

$1 \leq N \leq 1000$；

$1 \leq M \leq 300000$；

$1 \leq K \leq 10000$；

$1 \leq A_i , B_i \leq N , A_i \neq B_i$；

$1 \leq C_i \leq 10^9 , \forall i \neq j , C_i \neq C_j$；