请编写程序创建一个有向图。有向图中包含n个顶点,编号为0至n-1。 输入格式: 输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过20000。接下来e行表示每条边的信息,每行为3个非负整数a、b、c,其中a和b表示该边的端点编号,c表示权值。各边并非按端点编号顺序排列。 输出格式: 按顶点编号递增顺序输出每个顶点引出的边,每个顶点占一行,若某顶点没有引出边,则不输出。每行表示一个顶点引出的所有边,格式为a:(a,b,w)……,表示有向边a->b的权值为w,a引出的多条边按编号b的递增序排列。C语言要求尽可能简单
时间: 2024-02-18 07:05:02 浏览: 55
C语言程序设计-编写程序。从键盘读入8个整数存入数组a中并输出这8个数据。和、最大值、最小值及平均值。正数之和、负数之和
5星 · 资源好评率100%
以下是一个简单的C语言程序,用于创建有向图并输出每个顶点引出的边:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 20000
#define MAX_EDGES 20000
struct Edge {
int start;
int end;
int weight;
};
struct Node {
int id;
int num_edges;
struct Edge edges[MAX_EDGES];
};
int cmp_edge(const void *a, const void *b) {
struct Edge *edge1 = (struct Edge *)a;
struct Edge *edge2 = (struct Edge *)b;
return edge1->end - edge2->end;
}
int main() {
int n, e;
scanf("%d %d", &n, &e);
struct Node nodes[MAX_NODES];
for (int i = 0; i < n; i++) {
nodes[i].id = i;
nodes[i].num_edges = 0;
}
for (int i = 0; i < e; i++) {
int start, end, weight;
scanf("%d %d %d", &start, &end, &weight);
struct Edge edge = {start, end, weight};
nodes[start].edges[nodes[start].num_edges++] = edge;
}
for (int i = 0; i < n; i++) {
if (nodes[i].num_edges > 0) {
printf("%d:", i);
qsort(nodes[i].edges, nodes[i].num_edges, sizeof(struct Edge), cmp_edge);
for (int j = 0; j < nodes[i].num_edges; j++) {
printf("(%d,%d,%d)", nodes[i].edges[j].start, nodes[i].edges[j].end, nodes[i].edges[j].weight);
}
printf("\n");
}
}
return 0;
}
```
该程序定义了两个结构体:`Edge`表示一条边,包含起点、终点、权值三个属性;`Node`表示一个顶点,包含顶点编号、引出的边数和引出的边三个属性。由于题目中给出的e不超过20000,因此每个顶点引出的边最多也是20000条,所以可以直接使用数组来存储,不需要使用动态分配内存的方式。
程序首先定义了一个包含n个顶点的数组,每个顶点都有一个空数组用于存放引出的边。接着程序读入每条边的信息并将其加入到对应的顶点的引出边数组中。
最后程序遍历每个顶点,如果该顶点有引出的边,则按照终点编号递增的顺序排序后输出。注意输出格式中每行的末尾不能有空格。
阅读全文