请编写程序创建一个有向图。有向图中包含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 10:04:59 浏览: 80
以下是一个简单的C语言程序,用于创建有向图并输出每个顶点引出的边:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODES 20000
struct Edge {
int start;
int end;
int weight;
};
struct Node {
int id;
int num_edges;
struct Edge *edges;
};
void add_edge(struct Node *nodes, int start, int end, int weight) {
struct Edge edge = {start, end, weight};
nodes[start].edges[nodes[start].num_edges++] = edge;
}
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;
nodes[i].edges = malloc(sizeof(struct Edge) * e);
}
for (int i = 0; i < e; i++) {
int start, end, weight;
scanf("%d %d %d", &start, &end, &weight);
add_edge(nodes, start, end, weight);
}
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`表示一个顶点,包含顶点编号、引出的边数和引出的边三个属性。
然后程序通过输入参数创建了一个包含n个顶点的数组,每个顶点都有一个空数组用于存放引出的边。接着程序读入每条边的信息并将其加入到对应的顶点的引出边数组中。
最后程序遍历每个顶点,如果该顶点有引出的边,则按照终点编号递增的顺序排序后输出。注意输出格式中每行的末尾不能有空格。
阅读全文