← 返回比赛

已结束 GESP排位赛#7

← 上一题下一题 →

A1820 | $连通三元组$

时间限制3s

内存限制512MB

通过 / 提交0/0

题目描述

时间限制：3000ms 内存限制：512MB 给你一个有 $N$ 个顶点的无向图 $G$ 。 $G$ 使用 $N \times N$ 的邻接矩阵 $A$ 来表示。 若 $A_{i,j} = 1$ 表示顶点 $i$ 和 $j$ 之间有一条边，否则表示顶点 $i$ 和 $j$ 之间没有边连接。 如果一个三元组 $(i, j, k)$ 满足以下条件则被称为 $\bf{连通三元组}$ $(i,j,k)$： 顶点 $i$ 与 $j$ 之间有一条边，顶点 $j$ 与 $k$ 之间有一条边，顶点 $i$ 与 $k$ 之间有一条边。 即：$A_{i, j} = A_{j, k} = A_{i, k} = 1$。 求图中满足 $1 \le i \lt j \lt k \le N$ 的 $\bf{连通三元组}$ $(i,j,k)$ 的个数。 $\large{数据范围}$ - $3 \le N \le 3000$

输入格式

对于每个测试数据格式如下： $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}$

输出格式

对于每个测试数据在单独的一行中输出答案；

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出