TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1980
  • 题目
  • P1980【搜索】树形图计数
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    小 k 同学最近正在研究最小树形图问题。所谓树形图,是指有向图的一棵有根的生成树,其中树的每一条边的指向恰好都是从根指向叶结点的方向。现在小 k在纸上画了一个图,他想让你帮忙数一下这个图有多少棵树形图。

    输入格式

    第1行输入 1个正整数n,表示图中点的个数
    第2到第n+1行每行输入n个字符,描述了这个图的邻接矩阵。
    第i+1行第j个字符如果是0则表示没有从i连向j的有向边,1表示有一条从i到j的有向边。

    输出格式

    输出1行1个整数,表示这个有向图的树形图个数。

    样例输入

    4
    0100
    0010
    0001
    1000

    样例输出

    4

    提示

    对于100%的数据,n≤ 8.