33OJ
登录 注册

#P17808. [ICPC 2019 Nanchang R] Bob's Problem

[ICPC 2019 Nanchang R] Bob's Problem

题目描述

Bob 遇到了麻烦。他摩擦了手指上的魔戒,于是你从地底冒了出来。

给定一个无向图 GG,包含 nn 个顶点(编号 11 到 nn),以及 mm 条带权边,每条边被染成黑色或白色。你需要从 GG 中选择一些边,使得任意两个顶点之间都存在至少一条仅经过所选边的路径,同时你可以选择不超过 kk 条白边。满足条件的选边方案可能有多种,请你找出所选边总权重最大的一种方案。

输入格式

第一行包含一个整数 TT(1≤T≤51\leq T\leq 5),表示测试数据的组数。

对于每组测试数据,第一行包含三个整数 nn(1≤n≤500001 \le n \le 50000)、mm 和 kk(1≤k≤m≤5000001\le k\le m \le 500000)。

接下来的 mm 行,每行包含四个整数 u,vu, v(1≤u,v≤n1\le u,v\le n)、ww(0≤w≤1000000\le w\le 100000)和 cc(0≤c≤10\le c\le 1),描述一条连接第 uu 个顶点与第 vv 个顶点的边,其权重为 ww,颜色为 cc。若 c=1c = 1,则该边为白色;若 c=0c = 0,则为黑色。

注意,某些顶点之间可能存在多条边,图中也允许出现自环。

输出格式

对于每组测试数据,输出一行一个整数,表示所选边的最大总权重;如果对于给定的图不存在合法方案,则输出 -1。

1
5 6 2
1 2 0 0
1 3 5 1
1 5 1 0
2 3 6 1
2 4 2 0
3 4 7 1
16

提示

翻译由 DeepSeek V4 Pro 完成