Triangle

题目描述

给你一个有 $N$ 个顶点的简单无向图 $G$。 $G$ 以 $N \times N$ 的邻接矩阵 $A$ 给出。也就是说，当 $A_{i,j}$ 为 $1$ 时顶点 $i$ 和 $j$ 之间有一条边，若 $A_{i,j}$ 为 $0$ 则没有边。 求满足 $1 \le i < j < k \le N$ 的整数三元组 $(i,j,k)$ 的个数，使得顶点 $i$ 和 $j$ 之间有一条边，顶点 $j$ 和 $k$ 之间有一条边，且顶点 $i$ 和 $k$ 之间有一条边。

输入格式

输入按如下格式从标准输入给出： $N$ $A_{1,1}A_{1,2}\dots A_{1,N}$ $A_{2,1}A_{2,2}\dots A_{2,N}$ $\vdots$ $A_{N,1}A_{N,2}\dots A_{N,N}$

输出格式

输出答案。

4
0011
0011
1101
1110

2

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

0

提示

$3 \le N \le 3000$ $A$ 是一个简单无向图 $G$ 的邻接矩阵。 输入中的所有数值均为整数。$(i,j,k)=(1,3,4),(2,3,4)$ 满足条件。 $(i,j,k)=(1,2,3)$ 不满足条件，因为顶点 $1$ 和 $2$ 之间没有边。 因此，答案是 $2$.

标签: AtCoder|abc258G

来源

AtCoder|abc258G