#P17808. [ICPC 2019 Nanchang R] Bob's Problem
[ICPC 2019 Nanchang R] Bob's Problem
Problem Description
Bob was in trouble. He rubbed the magic ring on his finger, and you came out of the ground.
You are given an undirected graph which contains vertices labelled from to , with weighted edges between them coloured in black or white. You have to choose some edges in such that there is at least one path between any two vertices only passing by selected edges, and you can select no more than white edges. There may be multiple available strategies to determine these edges, and you are asked to find out the way with a maximum total weight of edges.
Input Format
The first line contains an integer () indicating the number of test cases.
For each test case, the first line contains three integers and .
Each of the following lines contains four integers and describing an edge of weight and colour between the -th vertex and the -th vertex. Here an edge is white if , or black if .
Note that there may be multiple edges between some vertices, and self-loops are also allowed.
Output Format
For each test case, output a single line with an integer indicating the maximum total weight of selected edges, or output -1 if there is no solution for the given graph.
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