PP4884 网的邻接矩阵2（基础）

这道题比"图的邻接矩阵"更进一步：图上每条边都带一个权值（可以理解成这条边的长度或花费），这样的图叫"网"。我们要把权值存进邻接矩阵并输出。

解题思路

第一步，理解权值矩阵。 邻接矩阵的格子 a[i][j] 不再只填 0 或 1，而是填结点 i 和 j 之间那条边的权值。题目规定：两个结点之间没有边时，格子填 999。

第二步，初始化矩阵。 先把整个矩阵都填成 999，包括对角线 a[i][i] 也填 999，因为自己和自己之间没有边。这一步不能省，否则没边的地方会输出 0，和题目要求不符。

第三步，写入权值。 这是"无向"的网，读入一条边 x y w，表示 x 和 y 之间有一条权值为 w 的边。无向意味着两个方向都能走，所以 a[x][y]=w、a[y][x]=w 都要写。比如样例 3 1 3，就在 a[3][1] 和 a[1][3] 都填 3。

第四步，输出矩阵。 逐行输出，同一行的数字之间用空格隔开。对照样例第一行是 999 2 3 8，意思是结点 1 到 2 的权值是 2，到 3 是 3，到 4 是 8，1 到 1 没有边所以是 999。

第五步，验证结果。 输出后可以用"对称性"自检：因为是无向网，矩阵应该关于对角线对称，a[i][j]==a[j][i]，如果发现不对称，多半是漏写了反向赋值。

参考代码

// 输入无向网的边和权值，建立邻接矩阵并输出，无边处用999
#include <iostream>
using namespace std;

int a[505][505];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = 999; // 初始全部无边
    for (int k = 0; k < m; k++) {
        int x, y, w;
        cin >> x >> y >> w;
        a[x][y] = w;
        a[y][x] = w; // 无向网，两个方向权值相同
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > 1) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

复杂度分析：初始化矩阵要 O(n²)，读入 m 条边要 O(m)，输出矩阵要 O(n²)，所以总时间复杂度 O(n²)，空间复杂度 O(n²)。n 是结点数，这个规模非常小。