城市交通网络构建

【题目描述】

某城市规划局正在整理辖区内的道路数据。该城市共有 n 个路口（编号为 0 到 n-1）以及 m 条连接这些路口的道路。

目前的道路系统比较复杂，包含两种类型：

1. 单行道：只能从一个路口通行到另一个路口。

2. 双行道：两个路口之间可以双向互通。

请你根据给定的道路信息，建立一个 n * n 的通达性矩阵，用来直观地展示各路口之间的直接连通情况。

【输入格式】

第一行包含两个正整数 n 和 m (1<=n, m <=100)，分别代表路口的数量和道路的数量。

接下来的 m 行，每行包含三个整数 type, u, v (0 <=type<= 1, 0<=u, v < n)，描述一条道路的信息：

• 当 type=0 时：表示这是一条单行道，仅允许从路口 u 通行到路口 v。

• 当 type=1 时：表示这是一条双行道，路口 u 和路口 v 之间可以互相通行。

【输出格式】

输出一个 n * n 的矩阵。

矩阵的第 i 行第 j 列的数值表示路口 i 到路口 j 的连通状态：

• 如果值为1，表示存在一条直接道路可以从 i 到达 j；

• 如果值为0，表示没有直接道路相连。

【输入样例】

4 4 0 0 1 1 0 2 0 3 1 1 2 3

【输出样例】

0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0

1. 核心概念

邻接矩阵是图论中最基础的存图方式。其本质是一个二维数组g[i][j]。

• 行与列：代表图中的点。

• 数值：代表点与点之间的关系（如连通性或权值）。

  • g[i][j] = 1：表示点i到点j有边。

  • g[i][j] = 0：表示点i到点j无边。

2. 代码实现要点

在处理混合图（同时包含有向边和无向边）时，只需在输入阶段做一个简单的if判断：

• 有向边：u -> v

  • 操作：仅需标记g[u][v] = 1。

  • 含义：只能从u去往v，反之不一定。

• 无向边：u <-> v

  • 操作：双向标记，即g[u][v] = 1且g[v][u] = 1。

  • 含义：既能从u到v，也能从v到u，等价于两条方向相反的有向边。

3. 复杂度分析

• 空间复杂度：O(N^2)。

  • 这是邻接矩阵最大的短板。如果 N=10000，这就需要开int g[10000][10000]，内存会直接爆炸（约为 400MB），通常题目给的 N <= 1000 时才考虑使用。

• 查询时间：O(1)。

  • 这是它的最大优势。想要知道点i和点j是否相连，直接查数组g[i][j]即可，速度极快。

4. 易错点提示

• 索引对应：题目中点的编号通常是从 0 开始（0 到 n-1）还是从 1 开始（1 到 n）。本题是 0 到 n-1，所以循环输出时是i=0; i<n。如果是 1 到 n，则需要i=1; i<=n。

• 初始化：全局变量数组会自动初始化为 0，如果在main函数内部定义数组，记得手动memset清零，否则可能会有随机垃圾值。

#include <iostream> using namespace std; int n,m; int g[101][101]; int main() { cin>>n>>m;//n个点 m条边 for(int i=1;i<=m;i++){ int type,u,v; cin>>type>>u>>v; if(type==0)//有向边 g[u][v]=1; else{//无向边当双向边处理 g[u][v]=1; g[v][u]=1; } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<g[i][j]<<" "; } cout<<endl; } return 0; }