#P17805. [ICPC 2019 Nanchang R] A Funny Bipartite Graph
[ICPC 2019 Nanchang R] A Funny Bipartite Graph
Problem Description
Bob is really interested in bipartite graph, and he needs help for this problem:
:::align{center}
:::
Bob has a bipartite graph which meets all the conditions below:
- The left part has () vertices, named . And the right part also has vertices, named .
- never connects with when for all pairs of that .
- For each vertex on the left part (), its degree is at most and at least ().
Bob wants to select some edges from the graph such that the selected edges and their endpoints form a new graph. However, he should obey these rules:
- Some pairs of vertices can't appear in the new graph together. You are given an matrix , is if and only if and can't appear in the new graph together.
- Bob must ensure that the selected edges cover all the right vertices. In other words, every right vertex should appear in the new graph.
- Every left vertex () has a magic number (). If appears in the new graph, its cost is , where is the degree of in the new graph, otherwise its cost is zero.
Now Bob wants to select edges satisfying the rules above with minimum total cost. Please write a program to help him find the minimum total cost, or determine it is impossible to get such a valid new graph.
Input Format
There are several test cases in the input file. The first line contains one integer () --- number of the test cases. For each case:
The first line contains one integer () --- number of the left vertices.
The following lines are about the graph edges information with an matrix . The -th line contains a 01-string and the -th character is if and only if and are connected, otherwise is . We guarantee that the degree of each left vertex is between and . We also guarantee that is always when .
The following line is empty.
The following lines are about the constraints on left vertices with an matrix . The -th line contains a 01-string and the -th character is if and only if and can't be both in , which is the set of endpoints of the selected edges. We guarantee that () is and ().
The following line is about magic numbers containing integers. The -th integer () is the magic number of .
Output Format
For every case print a single line containing an integer, the minimum total cost. If it is impossible to get such a valid new graph, just output -1 instead.
2
4
1100
0110
0001
0001
0001
0001
0000
1100
3 4 4 5
4
1100
0110
0001
0001
0011
0001
1000
1100
3 4 4 5
17
-1
Hint
In the first case:
:::align{center}
:::
We can choose edges such that , satisfies the matrix's constraints. And the degrees are , so the total cost .
In the second case, and can't be both covered at the same time, so there is no solution.