c语言输入格式: 输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过20000。接下来e行表示每条边的信息,每行为3个非负整数a、b、c,其中a和b表示该边的端点编号,c表示权值。各边并非按端点编号顺序排列。 输出格式: 按顶点编号递增顺序输出每个顶点引出的边,每个顶点占一行,若某顶点没有引出边,则不输出。每行表示一个顶点引出的所有边,格式为a:(a,b,w)……,表示有向边a->b的权值为w,a引出的多条边按编号b的递增序排列。
时间: 2024-02-18 19:04:47 浏览: 92
以下是完整的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 20005
#define MAXE 20005
struct Edge {
int from, to, weight, next;
} edges[MAXE];
int head[MAXN], cnt;
void addEdge(int from, int to, int weight) {
cnt++;
edges[cnt].from = from;
edges[cnt].to = to;
edges[cnt].weight = weight;
edges[cnt].next = head[from];
head[from] = cnt;
}
void buildGraph(int n, int e) {
for (int i = 1; i <= e; i++) {
int from, to, weight;
scanf("%d%d%d", &from, &to, &weight);
addEdge(from, to, weight);
}
}
void printGraph(int n) {
for (int i = 1; i <= n; i++) {
if (head[i] == 0) continue;
printf("%d:", i);
for (int j = head[i]; j != 0; j = edges[j].next) {
printf("(%d,%d,%d)", i, edges[j].to, edges[j].weight);
if (edges[j].next != 0) printf(",");
}
printf("\n");
}
}
int main() {
int n, e;
scanf("%d%d", &n, &e);
buildGraph(n, e);
printGraph(n);
return 0;
}
```
首先定义了一个结构体来表示边的信息。然后使用了一个 `head` 数组来记录每个顶点所连的第一条边的编号。在读入每条边时,调用 `addEdge` 函数来添加边,同时更新 `head` 数组。在输出时,遍历每个顶点,然后遍历它所连的所有边,输出即可。
需要注意的是,题目要求按顶点编号递增顺序输出每个顶点引出的边,因此在输出时需要从 1 到 n 依次遍历顶点,如果某个顶点没有引出边,则不输出。同时,为了保证边的编号 b 递增,我们可以在添加边时按照 b 的大小排序,即在 `addEdge` 函数中,遍历当前顶点的所有边,如果遇到一个编号比当前边大的边,则将当前边插入到这条边之前。
完整的 C++ 语言代码实现可以参考下面的代码:
阅读全文