输入样例: 第1行依次输入各个小岛对应得分(整数),即顶点的值,以-1结束(顶点不包含-1) 接下来若干行输入每条边的信息,格式为:v1空格v2(v1、v2为小岛对应的下标),直到输入‘-1 -1’结束。 0 1 2 3 4 5 6 -1 0 3 0 4 3 2 3 1 2 5 1 5 4 5 5 6 -1 -1 输出样例: 输出两行数据,第一行为行进路线,以小岛的积分(即顶点的值)作为小岛标识,每个标识之间间隔一个空格,第二行为一个整数,为最终获得积分。 0 3 1 5 2 4 6 21
时间: 2024-02-09 09:10:42 浏览: 28
以下是一个可能的实现方式,仅供参考:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode { // 边表结点
int adjvex; // 邻接点在数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点结点的指针
} ArcNode;
typedef struct VNode { // 顶点表结点
int data; // 顶点值
ArcNode *firstarc; // 指向第一个邻接点结点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图结构
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
int visited[MAX_VERTEX_NUM]; // 标记顶点是否被访问过
int path[MAX_VERTEX_NUM]; // 记录搜索路径
int pathlen = 0; // 记录搜索路径长度
int score = 0; // 记录总得分
void DFS(ALGraph *G, int v) {
visited[v] = 1; // 标记v已被访问
path[pathlen++] = v; // 将v加入搜索路径中
score += G->vertices[v].data; // 累加得分
ArcNode *p = G->vertices[v].firstarc; // 找到v的第一个邻接点
while (p) {
int w = p->adjvex; // 邻接点在数组中的下标
if (visited[w] == 0) { // 如果w未被访问过,则继续搜索
DFS(G, w);
}
p = p->nextarc; // 找到v的下一个邻接点
}
}
int main() {
ALGraph G;
int v1, v2;
int i, j;
// 读入顶点数和边数
scanf("%d%d", &G.vexnum, &G.arcnum);
// 读入顶点的值
for (i = 0; i < G.vexnum; i++) {
scanf("%d", &G.vertices[i].data);
G.vertices[i].firstarc = NULL; // 初始化邻接表
}
G.vertices[i].data = -1; // 最后一个顶点值为-1
// 读入边的信息
for (j = 0; j < G.arcnum; j++) {
scanf("%d%d", &v1, &v2);
if (v1 == -1 && v2 == -1) { // 输入结束标志
break;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->nextarc = G.vertices[v1].firstarc;
G.vertices[v1].firstarc = p;
}
// 对每个连通分量进行DFS搜索
for (i = 0; i < G.vexnum; i++) {
visited[i] = 0; // 初始化visited数组
}
for (i = 0; i < G.vexnum; i++) {
if (visited[i] == 0 && G.vertices[i].data != -1) {
pathlen = 0; // 初始化搜索路径
score = 0; // 初始化得分
DFS(&G, i);
printf("%d", path[0]);
for (j = 1; j < pathlen; j++) {
printf(" %d", path[j]);
}
printf(" ");
printf("%d\n", score);
}
}
return 0;
}
```
代码中,我们首先定义了一个有向图结构ALGraph,包括顶点数组和顶点数、边数两个属性。对于每个顶点,我们记录了它的值和邻接表(即以该顶点为起点的所有边组成的链表)。对于每条边,我们使用邻接表存储,即对于每个顶点,我们记录其指向的所有邻接点。
在main函数中,我们首先读入顶点数和边数,并依次读入每个顶点的值和每条边的信息。在读入边的信息时,我们通过邻接表的方式存储边。
接着,我们对每个连通分量进行DFS搜索。这里需要注意的是,当图不是连通图时,我们需要对每个连通分量分别进行搜索。在DFS搜索时,我们记录搜索路径和得分,最后将搜索结果打印出来即可。
需要注意的是,由于顶点值中可能包含负数,因此当求得总得分时需要累加每个顶点的值。另外,由于顶点的值可能为-1,因此在读入顶点值时需要在最后一个顶点后面加上一个-1,以作为输入结束标志。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)