UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3979. [WF2012]infiltration

统计 下载数据

Description

早上好,特工W-12,你需要完成的以下的任务。
我们已经渗透到一个叫混乱与祸害的组织中,希望能掌握该组织的管理权。不幸的是,它们似乎已经准备好应对这样的事件了,它们使用了一个很复杂的设计分配管理权力,这使得我们的渗透工作非常艰难。
那家组织的管理系统被分成若干个单位,对于任意两个单位A和B,要么A管理B要么B管理A,同时这个管理关系可以形成环,因此可以出现A管理B、B管理C、C管理A的情况。
我们可以安排特工去渗透到任意一个单位,那将使得我们控制该单位和那个单位直接管理的单位,但是不包括间接管理的单位。比如之前的样例,渗透到A单位会让我们控制A和B,但不能控制C。
对于一个成功的渗透工作来说,我们必须要控制所有的单位才行,否则其他单位会发现我们,同时破坏我们的计划。而你也知道,我们现在从更高的部门那里拿到的经费十分紧缺,我们必须最高效地完成任务。你的任务就是要找出控制单位最少的可行方案。

Input

第一行包含一个整数n,表示该组织的单位数。接下来n行每行n个二进制位。在其中的第i行第j列位置,若为1表示i单位控制j单位,否则j单位控制i单位

Output

共一行,第一个整数ans表示最少的控制单位数量

Sample Input

2
00
10
3
010
001
100
5
01000
00011
11001
10100
10010
4
0100
0000
1100
1110
4
0011
1011
0001
0000
4
0101
0010
1001
0100
6
001110
100001
010010
011010
010001
101100
4
0000
1001
1100
1010
7
0100011
0000100
1100001
1110111
1010011
0110000
0100010
7
0010001
1011111
0001111
1000110
1000000
1000100
0001110

Sample Output

Case 1: 1
Case 2: 2
Case 3: 2
Case 4: 1
Case 5: 1
Case 6: 2
Case 7: 2
Case 8: 2
Case 9: 1
Case 10: 1

Hint

100%的数据n<=75。

保证n*n的01矩阵中所有的i行i列位置为0,i行j列和j行i列两个位置恰好一个为1一个为0(i≠j)。


Source