#3979. [WF2012]infiltration

题目描述

早上好，特工W-12，你需要完成的以下的任务。

我们已经渗透到一个叫混乱与祸害的组织中，希望能掌握该组织的管理权。不幸的是，它们似乎已经准备好应对这样的事件了，它们使用了一个很复杂的设计分配管理权力，这使得我们的渗透工作非常艰难。

那家组织的管理系统被分成若干个单位，对于任意两个单位A和B，要么A管理B要么B管理A，同时这个管理关系可以形成环，因此可以出现A管理B、B管理C、C管理A的情况。

我们可以安排特工去渗透到任意一个单位，那将使得我们控制该单位和那个单位直接管理的单位，但是不包括间接管理的单位。比如之前的样例，渗透到A单位会让我们控制A和B，但不能控制C。

对于一个成功的渗透工作来说，我们必须要控制所有的单位才行，否则其他单位会发现我们，同时破坏我们的计划。而你也知道，我们现在从更高的部门那里拿到的经费十分紧缺，我们必须最高效地完成任务。你的任务就是要找出控制单位最少的可行方案。

输入格式

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

输出格式

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

样例

样例输入

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  

样例输出

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  

数据范围与提示

100%的数据n<=75。

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