Description

你有足够多的象棋“车”，在一个n×n的棋盘上你能放多少个“车”呢？注意，所给棋盘上有些位置不能放任何东西。同时，某一行（列）最多只能存在一个“车”。

Input Format

第一行为一个正整数n。（1<=n<=500 ）

接下来n行，每行包含n个整数，若为0表示这个位置不能放“车”；若为1表示这个位置可以放“车”。

Output Format

输出一个整数，表示最多能放多少个“车”。

5
1 0 0 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 0
0 0 0 1 0​

3​

Source

图论 二分图