B3600.md

[图论与代数结构 101] 图的代数表示

题目描述

给定一张 $n$ 个点 $m$ 条边的图，有可能存在重边和自环。请你给出这张图所有的代数表示。

输入格式

第一行四个正整数 $n$，$m$，$type1$ 和 $type2$。其中 $n$ 和 $m$ 分别表示图的点数和边数。$type1 = 0$ 表示该图为无向图，$type1 = 1$ 表示该图为有向图。$type2 = 0$ 表示该图不是赋权图，$type2 = 1$ 表示该图是赋权图。

如果 $type2 = 0$，接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ 表示一条边。

如果 $type2 = 1$，接下来 $m$ 行，每行三个正整数 $u$ ， $v$ 和 $d$ 表示一条边，其中 $d$ 为这条边的边权。

输出格式

按顺序输出下列代数表示：

1. 邻接矩阵或权矩阵。输出 $n$ 行，每行 $n$ 个数表示矩阵。如果该图存在重边则不输出。如果 $type2 = 0$ 输出邻接矩阵，如果 $type2 = 1$ 输出权矩阵。

2. 关联矩阵。输出 $n$ 行，每行 $m$ 个数表示矩阵。如果 $type2 = 1$ 或有自环则不输出。

3. 邻接表。输出 $n$ 行。如果 $type2 = 0$ 每行输出 $d _ i$ 个数，其中 $d _ i$ 为节点 $i$ 的度数（无向图）或正度（有向图），每个数表示一条与 $i$ 相接的边。如果 $type2 = 1$ 每行输出 $2d _ i$ 个数，每两个数表示一条边。

4. 正向表。如果 $type2 = 0$ 输出两行，分别表示向量 $A$ 和向量 $B$ 。如果 $type2 = 1$ 输出三行，分别表示向量 $A$，向量 $B$ 和向量 $Z$。

5. 逆向表。如果 $type1 = 0$ 则不输出（因为此时逆向表与正向表相同）。如果 $type2 = 0$ 输出两行，分别表示向量 $A$ 和向量 $B$ 。如果 $type2 = 1$ 输出三行，分别表示向量 $A$，向量 $B$ 和向量 $Z$。

其中，邻接表、正向表、逆向表每个点对应的所有边按输入顺序输出。

正向表与逆向表的 $A$向量是 $n + 1$ 维向量，有向图中 $A(n + 1) = m + 1$，无向图中 $A(n + 1) = 2m + 1$。

样例 #1

样例输入 #1

3 3 0 0
2 3
1 3
1 2

样例输出 #1

0 1 1
1 0 1
1 1 0
0 1 1
1 0 1
1 1 0
3 2
3 1
2 1
1 3 5 7
3 2 3 1 2 1

样例 #2

样例输入 #2

3 3 1 1
3 1 5
2 2 4
3 1 3

样例输出 #2

2 4
1 5 1 3
1 1 2 4
2 1 1
4 5 3
1 3 4 4
3 3 2
5 3 4

样例 #3

样例输入 #3

3 3 0 1
1 3 5
2 2 3
2 3 1

样例输出 #3

0 0 5
0 3 1
5 1 0
3 5
2 3 2 3 3 1
1 5 2 1
1 2 5 7
3 2 2 3 1 2
5 3 3 1 5 1

样例 #4

样例输入 #4

4 3 0 1
3 3 5
2 4 6
2 4 7

样例输出 #4

4 6 4 7
3 5 3 5
2 6 2 7
1 1 3 5 7
4 4 3 3 2 2
6 7 5 5 6 7

提示

对于所有数据，满足 $1 \le n \le 300$，$1 \le m \le 300$，$1 \le 边权 \le 32768$。

细节提示：

1.无向图中一些数组可能需要 $2 m$ 的长度，请仔细检查以免数组开小。

2.无向图中如果存在自环，则在邻接表和正向表中都需要将这条边输出两次，但不影响邻接矩阵或权矩阵的输出。

3.逆向表中对于连向一点的边也要按输入顺序输出而不是边权大小顺序。

4.无向带权图中每条非自环边都会修改权矩阵中两个位置。

5.无法通过时可以通过构造有向/无向、带权/不带权、有/无自环、有/无重边的小数据来检查代码。

样例一解释

第 $1$ 行至第 $3$ 行是邻接矩阵；

第 $4$ 行至第 $6$ 行是关联矩阵；

第 $7$ 行至第 $9$ 行是邻接表；

第 $10$ 行至第 $11$ 行是正向表。

样例二解释

第 $1$ 行至第 $2$ 行是邻接表；

第 $3$ 行至第 $5$ 行是正向表；

第 $6$ 行至第 $8$ 行是逆向表。