第一行包含两个整数 n n n 和 m m m。
接下来 m m m 行，每行包含三个整数 u u u, v v v, w w w，表示点 u u u 和点 v v v 之间存在一条权值为 w w w 的边。
输入4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4输出
邻接矩阵表示法： - 1 2 3 1 - 2 - 2 2 - 4 3 - 4 - 邻接表表示法(括号内为权值)： 与1相连的边有：4(3) 3(2) 2(1) 与2相连的边有：3(2) 1(1) 与3相连的边有：4(4) 2(2) 1(2) 与4相连的边有：3(4) 1(3)c++ 代码
#include邻接表转换成邻接矩阵 输入格式#include #include using namespace std; const int N = 510, M = 100010, INF = 0x3f3f3f3f; int n, m; int g[N][N]; // 邻接矩阵 struct Node { int id; // 编号 int w; // 权值 Node* next; Node(int _id, int _w) : id(_id), w(_w), next(NULL){} } *head[N]; // 邻接表 void add(int a, int b, int w) { Node* p = new Node(b, w); p->next = head[a]; head[a] = p; } void convert() // 邻接矩阵转换成邻接表 { for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (g[i][j] < INF / 2) add(i, j, g[i][j]); } int main() { memset(g, 0x3f, sizeof g); cin >> n >> m; while (m -- ) { int a, b, w; cin >> a >> b >> w; g[a][b] = g[b][a] = min(g[a][b], w); } puts("邻接矩阵表示法："); for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) if (g[i][j] > INF / 2) cout << '-' << ' '; else cout << g[i][j] << ' '; cout << endl; } convert(); puts("n邻接表表示法(括号内为权值)："); for (int i = 1; i <= n; i ++ ) { printf("与%d相连的边有：", i); for (auto p = head[i]; p; p = p->next) printf("%d(%d) ", p->id, p->w); cout << endl; } return 0; }
第一行包含两个整数 n n n 和 m m m。
接下来 m m m 行，每行包含三个整数 u u u, v v v, w w w，表示点 u u u 和点 v v v 之间存在一条权值为 w w w 的边。
输入4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4输出
邻接表表示法(括号内为权值)： 与1相连的边有：4(3) 3(2) 2(1) 与2相连的边有：3(2) 1(1) 与3相连的边有：4(4) 2(2) 1(2) 与4相连的边有：3(4) 1(3) 邻接矩阵表示法： - 1 2 3 1 - 2 - 2 2 - 4 3 - 4 -c++ 代码
#include#include #include using namespace std; const int N = 510, M = 100010, INF = 0x3f3f3f3f; int n, m; int g[N][N]; // 邻接矩阵 struct Node { int id; // 编号 int w; // 权值 Node* next; Node(int _id, int _w) : id(_id), w(_w), next(NULL){} } *head[N]; // 邻接表 void add(int a, int b, int w) { Node* p = new Node(b, w); p->next = head[a]; head[a] = p; } void convert() // 邻接表转换成邻接矩阵 { for (int i = 1; i <= n; i ++ ) { for (auto p = head[i]; p; p = p->next) { int j = p->id; // 与i相邻的点的编号 g[i][j] = g[j][i] = p->w; } } } int main() { memset(g, 0x3f, sizeof g); cin >> n >> m; while (m -- ) { int a, b, w; cin >> a >> b >> w; // 假设没有重边 add(a, b, w); add(b, a, w); } puts("邻接表表示法(括号内为权值)："); for (int i = 1; i <= n; i ++ ) { printf("与%d相连的边有：", i); for (auto p = head[i]; p; p = p->next) printf("%d(%d) ", p->id, p->w); cout << endl; } convert(); puts("n邻接矩阵表示法："); for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= n; j ++ ) if (g[i][j] > INF / 2) cout << '-' << ' '; else cout << g[i][j] << ' '; cout << endl; } return 0; }
