#P18335. Red-Blue MST
Red-Blue MST
Red-Blue MST
给定一张有 个顶点的连通无向图。每条边都有正整数权值,并被涂成红色或蓝色。
对于每个 ,求恰好包含 条红边的生成树的最小总权值;如果这样的生成树不存在,则报告不存在。
输入格式
第一行包含测试用例数 。
每组测试用例的第一行包含两个整数 ,表示顶点数和边数。
接下来 行,每行包含三个整数 ,后跟一个字符 ,表示一条端点为 、权值为 的无向边。字符 R 表示红色,B 表示蓝色。
保证整张图连通,没有自环。允许重边,同一对端点之间可以有多条边,包括颜色相同或不同的边。
输出格式
对于每组测试用例,输出一行 个整数 。
是恰好包含 条红边的生成树的最小总权值。如果不存在,则 。
数据范围
- ;
- ;
- ;
- ,;
- ;
- ;
- 所有测试用例的 之和不超过 ;
- 所有测试用例的 之和不超过 。
样例输入 1
2
4 6
1 2 1 R
2 3 5 B
3 4 1 R
4 1 5 B
1 3 1 R
2 4 3 B
3 3
1 2 5 R
1 3 7 R
2 3 9 B
样例输出 1
13 9 5 3
-1 14 12