Matching

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

Compute the maximum cardinality matching of given undirected graph \(G\).

Input

The first line contains one integer \(n\), which denotes the number of nodes.

The following \(n\) lines denotes the adjacency matrix \(A\) of graph \(G\).

(\(1 \leq n \leq 100\), \(A_{i, j} \in \{0, 1\}\), \(A_{i, i} = 0\), \(A_{i, j} = A_{j, i}\))

Output

The only integer equals to the size of maximum cardinality matching.

Sample Input

3
0 1 1
1 0 1
1 1 0

Sample Output

1

Hint

One of possible matchings is to pair node \(1\) and \(2\), leaving node \(3\) alone.

Source

ftiasch

Manager

Information
Solved Number52
Submit Number78
Problem Tags
graphs
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel