四面楚歌

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 virus.in 输出文件 virus.out

【题目描述】
公元2008年10月31日星期五,笃志者所在的整个机房由于猖獗的病毒一片恐慌。经查证,病毒是由A1机器散播开来的。。这要追溯到29日,笃志者由于病毒被迫从A1机器撤离。
一想到病毒是从自己的机器传开的,笃志者就心神不宁。他决定搞清楚病毒是怎么散播开来的。事实上,机房内的机器并不是全部都能够互相感染的。笃志者(ceeji)好不容易经过测试得到了机房中各机器间是否连通的图表,就在他马上就要得出结果的时候,大脑突然乱了!问题的严重性在于:如果他不在1s内搞清楚这个问题,机房就会整体瘫痪。现在笃志者求助于你,他需要知道病毒从未感染机房开始,最少入侵几台机器之后,机房就会整体感染。
【输入格式】
文件的第一行为一个整数n,第二行至第n+1行为n*n的矩阵(若第i行第j列为1,则机器i能对机器j进行ARP攻击(即感染机器j),若第i行第j列为0,则机器i不能感染机器j)。
文件名为“2.in”。
【输出格式】
输出文件只有一行,为笃志者想知道的最少感染机器数。
文件名为“2.out”。
【输入样例】
8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0
【输出样例】
2
【数据范围】
对于 100% 的数据,n<=1000