#E. [JSOI2010] 连通数

Type: RemoteJudge

300ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

度量一个有向图连通情况的一个指标是连通数，指图中可达顶点对个的个数。

如图

顶点 $1$ 可达 $1, 2, 3, 4, 5$

顶点 $2$ 可达 $2, 3, 4, 5$

顶点 $3$ 可达 $3, 4, 5$

顶点 $4, 5$ 都只能到达自身。

所以这张图的连通数为 $14$ 。

给定一张图，请你求出它的连通数

输入数据第一行是图顶点的数量，一个正整数 $N$ 。
接下来 $N$ 行，每行 $N$ 个字符。第 $i$ 行第 $j$ 列的 1 表示顶点 $i$ 到 $j$ 有边，0 则表示无边。

输出一行一个整数，表示该图的连通数。

对于 $100 \%$ 的数据， $1 \le N \le 2000$ 。