문제1594--AddElectricalWires

1594: AddElectricalWires

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 157  통과: 36
[제출] [채점기록] [묻고답하기]

문제 설명

You are given an electrical circuit for a home, with a number of nodes possibly connected by wires. Any pair of nodes may be connected by at most one wire, and a node can't be connected to itself. Each node on the circuit is either an electrical outlet for the house or a connection to the main electrical grid. The matrix of characters W tells you the wires that are already in place; the xth character of the yth row is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. The list of integers lists the indices of the nodes that are connections to the main electrical grid. 
You'd like to make the circuit safer and more redundant by adding as many extra wires to it as possible. The one complication is that no two main grid connections are currently wired together (directly or indirectly), and you must preserve this, or else disaster will result. Determine the maximum number of new wires you can add to the circuit.

입력 설명

The first line of the input gives a number of test cases, T.
The first line of each case gives the number of nodes N (1 <= N <= 50), the number of elements in G.
The next line contains each elements of G.
Next N line contains each element of W.

출력 설명

For each test case, output the maximum number of new wires on each line.

입력 예시 Copy

3
3 1
0
000
000
000
3 2
0 1
000
000
000
2 1
0
01
10

출력 예시 Copy

3
1
0

출처/분류