#P17808. [ICPC 2019 Nanchang R] Bob's Problem
[ICPC 2019 Nanchang R] Bob's Problem
题目描述
Bob 遇到了麻烦。他摩擦了手指上的魔戒,于是你从地底冒了出来。
给定一个无向图 ,包含 个顶点(编号 到 ),以及 条带权边,每条边被染成黑色或白色。你需要从 中选择一些边,使得任意两个顶点之间都存在至少一条仅经过所选边的路径,同时你可以选择不超过 条白边。满足条件的选边方案可能有多种,请你找出所选边总权重最大的一种方案。
输入格式
第一行包含一个整数 (),表示测试数据的组数。
对于每组测试数据,第一行包含三个整数 ()、 和 ()。
接下来的 行,每行包含四个整数 ()、()和 (),描述一条连接第 个顶点与第 个顶点的边,其权重为 ,颜色为 。若 ,则该边为白色;若 ,则为黑色。
注意,某些顶点之间可能存在多条边,图中也允许出现自环。
输出格式
对于每组测试数据,输出一行一个整数,表示所选边的最大总权重;如果对于给定的图不存在合法方案,则输出 -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 完成