输入格式: 输入第一行为两个正整数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:45 浏览: 188
无向图连通子图_并查集.cpp 最小生成树.cpp
好的,这是一道关于图的题目,需要读取输入数据,建立图的数据结构,然后输出每个顶点引出的边。那么我们可以先定义一个结构体来表示边的信息:
```
struct Edge {
int from, to, weight;
};
```
然后读取输入数据,建立图的数据结构,可以使用邻接表来表示图。我们可以使用一个vector<int>数组来表示每个顶点所连的边的编号,再使用一个vector<Edge>数组来存储所有的边。具体实现如下:
```
int n, e;
vector<int> head;
vector<Edge> edges;
void addEdge(int from, int to, int weight) {
edges.push_back({from, to, weight});
int m = edges.size();
head.resize(max(head.size(), (size_t)from + 1));
head[from] = (head[from] ? min(head[from], m) : m);
}
void buildGraph() {
cin >> n >> e;
for (int i = 0; i < e; i++) {
int from, to, weight;
cin >> from >> to >> weight;
addEdge(from, to, weight);
}
}
```
这里使用了一个addEdge函数来添加边,同时用head数组来记录每个顶点所连的第一条边的编号。
接下来就是输出每个顶点引出的边了,可以遍历每个顶点,然后遍历它所连的所有边,输出即可。具体实现如下:
```
void printGraph() {
for (int i = 1; i <= n; i++) {
if (head[i] == 0) continue;
cout << i << ":";
for (int j = head[i]; j != 0; j = edges[j-1].next) {
cout << "(" << i << "," << edges[j-1].to << "," << edges[j-1].weight << ")";
if (edges[j-1].next != 0) cout << ",";
}
cout << endl;
}
}
```
这里使用了一个next字段来记录每条边所连的下一条边的编号,如果没有下一条边,则next为0。在输出时,我们可以从head[i]开始,遍历到下一条边为0为止,输出每条边的信息即可。
完整代码如下:
阅读全文