邻接矩阵里:第 m 行 1 的个数是"出",第 m 列 1 的个数是"入",两者相加即答案。
题目来源:[GESP样题 七级] 迷宫统计(洛谷 P10265)。
幻想大陆上有 n 个迷宫,编号 1 ~ n。有的迷宫之间可以直接往返,有的可以走到别的迷宫、但走不回来。小杨决定从 m 号迷宫出发,需要统计:m 号迷宫可以直接到达其他迷宫有多少、有多少迷宫可以直接到达 m 号迷宫,以及这两个数的和。
注意:对于任意 i(1 ≤ i ≤ n),i 号迷宫总可以直接到达自身。
输入格式:第一行两个整数 n 和 m;接下来 n 行,每行 n 个整数,第 i 行第 j 列的整数为 1 表示能从 i 号迷宫直接到达 j 号迷宫,为 0 表示不能。
输出格式:一行输出空格分隔的三个整数,依次是"m 可以直接到达的迷宫数"、"能直接到达 m 的迷宫数"、"两者的总和"。
邻接矩阵出度 / 入度只统计"直接"到达对角线计入O(n²)
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 n 行 n 列的 0/1 矩阵 |
| 输出 | 出 入 和 三个整数,空格分隔、顺序固定 |
| 数据范围 | 1 ≤ m ≤ n ≤ 1000 |
| 矩阵含义 | a[i][j] = 1 ⟺ i 号能直接到达 j 号 |
| 特殊约定 | a[i][i] = 1:每个迷宫总能直接到达自身 |
| 子任务 | n ≤ 10(30 分)、n ≤ 100(30 分)、n ≤ 1000(40 分) |
a[行][列],"行"是出发地、"列"是目的地,所以 a[m][j] 回答"m 能直达谁",a[i][m] 回答"谁能直达 m"a[m][m] = 1,它同时落在第 m 行与第 m 列上,所以"出"和"入"各自至少是 1int 绰绰有余先把样例的邻接矩阵摆出来:行号在最左边,列号在最上面。
| 迷宫 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 1 | 0 | 0 | 1 |
| 4 | 0 | 0 | 1 | 1 | 0 | 1 |
| 5 | 0 | 0 | 0 | 1 | 1 | 0 |
| 6 | 1 | 0 | 0 | 0 | 1 | 1 |
目标是 4 号迷宫,所以只看第 4 行(数出)和第 4 列(数入)。
第 4 行 = 0 0 1 1 0 1
为 1 的是第 3、4、6 列
所以 4 号能直达 3、4、6 号迷宫 —— 共 3 个
其中第 4 个 1 就是"4 能到达自己"
✅ 出 = 3
第 4 列自上而下 = 1 0 0 1 1 0
为 1 的是第 1、4、5 行
所以 1、4、5 号能直达 4 号迷宫 —— 共 3 个
其中第 4 个 1 同样是"自己到达自己"
✅ 入 = 3
3 + 3 = 6
按"出、入、和"的顺序打印
✅ 3 3 6(与样例一致)
a[i][i] = 1 的必然结果,不是重复计数,千万不要"去重"。只想着"到达别的迷宫"的人,很容易把最小规模做成 0 0 0;只想着"只数别的迷宫"的人,又容易在全 1 矩阵上翻车。这两种极端都要亲手算一遍。
| 情形 | 矩阵 | 第 m 行 1 的个数 | 第 m 列 1 的个数 | 输出 |
|---|---|---|---|---|
| n = 1,m = 1 | 1 | 1(自己) | 1(自己) | 1 1 2 |
| n = 3,m = 2,只有对角线为 1 | 1 0 0 / 0 1 0 / 0 0 1 | 1(自己) | 1(自己) | 1 1 2 |
n = 2,m = 1,矩阵 1 1 / 0 1 | 1 1 / 0 1 | 2(1 号、2 号) | 1(1 号自己) | 2 1 3 |
| n = 4,m = 4,全 1 矩阵 | 四行都是 1 1 1 1 | 4 | 4 | 4 4 8 |
1 1 2 而不是 0 0 0。4 4 8:4 号能直达全部 4 个迷宫,也被全部 4 个迷宫直达。把这两个极端都算过,才能确认自己对"自身计入"和"输出顺序"没理解错。读完矩阵后,扫第 m 行得到"出"、扫第 m 列得到"入"
从 m 出发搜索,统计能走到的迷宫数
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 直接数行列(正解) | O(n²) 读入 + O(n) 统计 | 约 5 行 |
| BFS / DFS 求可达 | O(n²) | 约 30 行(而且题意错了) |
| Floyd 传递闭包 | O(n³) = 10⁹ | ❌ 超时 |
第一行输入 n 和 m,随后 n 行每行 n 个 0/1(代表邻接矩阵)。程序会数出第 m 行的 1、第 m 列的 1 以及它们的和。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[1005][1005]; // 邻接矩阵,开全局避免爆栈 int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]); int outDeg = 0, inDeg = 0; for (int j = 1; j <= n; j++) // 第 m 行:m 能直达谁 if (a[m][j] == 1) outDeg++; for (int i = 1; i <= n; i++) // 第 m 列:谁能直达 m if (a[i][m] == 1) inDeg++; printf("%d %d %d\n", outDeg, inDeg, outDeg + inDeg); return 0; }
a[m][j](m 固定、j 变化),数列时用 a[i][m](i 变化、m 固定)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
int a[1005][1005]; | 存矩阵 | n ≤ 1000,1005² 个 int ≈ 4 MB;开全局避免放在栈上爆栈 |
a[m][j] | 第 m 行 | 行 = 出发:统计 m 能直达哪些迷宫 |
a[i][m] | 第 m 列 | 列 = 到达:统计哪些迷宫能直达 m |
printf("%d %d %d", outDeg, inDeg, ...) | 输出顺序 | 题目要求顺序是出、入、和,顺序换了就错 |
a[i][i] 恒为 1 | 自身计入 | 对角线让 outDeg、inDeg 各自至少为 1 |
1000 × 1000 的数组开在 main 里(约 4 MB 栈空间,可能直接崩溃)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 4 | 3 3 6 | 题面样例 1 |
1 1 | 1 1 2 | 最小规模:只有自己,"1 1 2"而不是"0 0 0" |
3 2 | 1 1 2 | 只有对角线为 1:谁也到不了别人 |
2 1 | 2 1 3 | 1 号能直达 1、2 两个;只有 1 号(自己)能直达 1 号 |
4 4 | 4 4 8 | 全 1 矩阵:4 号直达全部 4 个,也被全部 4 个直达 |
5 3 | 4 3 7 | 第 3 行有 4 个 1、第 3 列有 3 个 1,注意行列入不相同 |
1 1 2 吗?⑤ 矩阵开成全局数组了吗?m(行)、一个也是 m(列),但变化的那一维位置不同,务必写清 a[m][j] 与 a[i][m]。a[i][i] = 1 是题目约定,第 m 行/第 m 列里的"自己"必须计入,漏掉就会少 1(甚至少 2)。邻接矩阵 1005 × 1005 个 int ≈ 4 MB,远低于 256 MB 内存限制;开成全局数组即可。
✅ 约 100 万次操作,1 秒时限内不到 1 毫秒。本题真正的瓶颈是读入矩阵,统计部分只有 O(n)——所以哪怕把统计写成 O(n²) 也毫无影响。
// 行 = 出,列 = 入 int outDeg = 0, inDeg = 0; for (int j = 1; j <= n; j++) if (a[m][j]) outDeg++; // 第 m 行 for (int i = 1; i <= n; i++) if (a[i][m]) inDeg++; // 第 m 列 // ② 更省事:读入时顺手把"度"统计好,事后不必再扫两遍 int oDeg[1005] = {0}, iDeg[1005] = {0}; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); if (a[i][j] == 1) { oDeg[i]++; iDeg[j]++; } // 一条边 i -> j 的贡献 } // 此时答案就是 oDeg[m]、iDeg[m]、oDeg[m] + iDeg[m] // ③ 输入共 n² = 10⁶ 个数字,用 scanf 足够快(不加 sync_with_stdio 的 cin 会慢很多)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 邻接矩阵读法 | 行 = 出发、列 = 到达 | 所有"看矩阵数关系"的入门图论题 |
| 度计数 | 一条边 u → v 让 outDeg[u]++、inDeg[v]++ | 拓扑排序、欧拉路径、网络流建图 |
| 只统计"直接"关系 | 只扫一层,不做多步搜索 | 单步关系统计题(别过度设计) |
| 输入规模估算 | n² = 10⁶,判断该用 O(n²) 还是更快 | 所有题的第一步:先算运算量 |