/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 頂点単純無向グラフ G が与えられます。
G は N 行 N 列の隣接行列 A によって与えられます。つまり、A_{i,j} が 1 である場合は頂点 i,j 間に辺があることを、0 である場合には辺がないことを意味します。
1 \le i < j < k \le N を満たす整数の組 (i,j,k) のうち、頂点 i,j 間にも頂点 j,k 間にも頂点 i,k 間にも辺があるようなものの個数を求めてください。
制約
- 3 \le N \le 3000
- A は単純無向グラフ G の隣接行列である。
- 入力はすべて整数。
入力
入力は以下の形式で標準入力から与えられる。
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
4 0011 0011 1101 1110
出力例 1
2
(i,j,k)=(1,3,4),(2,3,4) が条件を満たします。
(i,j,k)=(1,2,3) は、頂点 1,2 間に辺がないため条件を満たしません。
よって、解は 2 です。
入力例 2
10 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
出力例 2
0
Score : 600 points
Problem Statement
You are given a simple undirected graph G with N vertices.
G is given as the N \times N adjacency matrix A. That is, there is an edge between Vertices i and j if A_{i,j} is 1, and there is not if A_{i,j} is 0.
Find the number of triples of integers (i,j,k) satisfying 1 \le i < j < k \le N such that there is an edge between Vertices i and j, an edge between Vertices j and k, and an edge between Vertices i and k.
Constraints
- 3 \le N \le 3000
- A is the adjacency matrix of a simple undirected graph G.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
4 0011 0011 1101 1110
Sample Output 1
2
(i,j,k)=(1,3,4),(2,3,4) satisfy the condition.
(i,j,k)=(1,2,3) does not satisfy the condition, because there is no edge between Vertices 1 and 2.
Thus, the answer is 2.
Sample Input 2
10 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
Sample Output 2
0