TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1121
  • 問題
  • P1121消息的传递
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    时间:三国时期 ;地点:许昌;人物:曹操,你。
    事件:
    起因:曹操得知许昌城里有n个袁绍的奸细。(他们编号为1到n,奸细间存在着一 种消息传递关系,即若C[i][j]=1,表示奸细i能直接把消息传给奸细j)。
    经过:曹操想发布一个假消息,需要传达给所有奸细。曹操命令你来负责消息的发布。
    结果:聪明的你把消息传递给了很少的几个奸细,就使所有奸细都得到了这个消息。问:最少传递给几个奸细就能完成任务?

    入力形式

    第一行为N,第二行至第N+1行为N*N的矩阵(若第I行第J列为1,则奸细I能将消息直接传递给奸细J,若第I行第J列为0,则奸细I不能直接将消息传给J )

    出力形式

    你最少要传递的奸细的个数

    サンプル入力

    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

    ヒント

    N<=1000