解题思路

题目中给出的“相对静止”满足：

$a_{i,i}=1$
$a_{i,j}=a_{j,i}$
具有传递性

因此，这个关系本质上是一个等价关系。

P4688.第1题-列车相对静止问题

1000ms

Tried: 87

Accepted: 36

Difficulty: 3

所属公司 : 阿里

算法与标签>DFS

题目内容

一天，一群列车约好一起赛跑，在赛跑过程中，列车之间可能产生相对静止现象，即速度相等时看起来好像静止。现在给定 $n$ 辆列车的相对静止矩阵信息，其中至少存在一辆列车真正静止。请你计算可能真正静止的列车数量的最小值和最大值

输入描述

第一行输入整数 $n (1 ≤ n ≤ 500)$ 表示列车数量。

此后 $n$ 行，每行输入 $n$ 个整数 $a_{i,j}$ ( $1 ≤ i, j ≤ n$ ; $a_{i,j}$ ∈ { $0, 1$ })，其中 $a_{i,j }= 1$ 表示第 $i$ 辆列车与第 $j$ 辆列车相对静止，否则不相对静止；并且保证 $a_{i,i} = 1$ 且 $a_{i,j }= a_{j,i}$ 。保证相对静止关系具有传递性，即若 $i, j$ 相对静止且 $j, k$ 相对静止，则 $i, k$ 必然相对静止

输出描述

输出两个整数，分别表示可能的最小值和最大值。两数之间用空格分隔。

样例1

输入

2
1 0
0 1

输出

1 1

输入

预期输出（选填）

解题思路

P4688.第1题-列车相对静止问题

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About