输入格式: 第1行依次输入各个小岛对应得分(整数),即顶点的值,以-1结束(顶点不包含-1) 接下来若干行输入每条边的信息,格式为:v1空格v2(v1、v2为小岛对应的下标),直到输入‘-1 -1’结束。 输出格式: 输出两行数据,第一行为行进路线,以小岛的积分(即顶点的值)作为小岛标识,每个标识之间间隔一个空格,第二行为一个整数,为最终获得积分,无换行。
时间: 2024-03-06 10:47:45 浏览: 33
明白了,您需要我对代码进行修改以实现输入输出。我已经修改好了,您可以看一下下面的代码,如果有需要可以再进行调整。
```c
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
int visited[MVNum];
typedef struct{
int vexs[MVNum]; //顶点向量,各小岛对应积分
int arcs[MVNum][MVNum]; //邻接矩阵
int vexnum,arcnum; //顶点数,边数
}AMGraph;
int LocateVex(AMGraph G,int u) //查询顶点u的下标
{
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vexs[i])
return i;
return -1;
}
void CreateUDG(AMGraph &G); //创建图,采用邻接矩阵存储
int DFS(AMGraph G, int v, int *path, int *max_score);//以v为起点深度优先遍历,求出各顶点值的和作为返回值
int main()
{
AMGraph G;
int i, j;
int path[MVNum]; //存储路径
int max_score = 0; //最大积分
int start_point;
//输入岛屿积分
i = 0;
while(scanf("%d", &G.vexs[i]) && G.vexs[i] != -1){
++i;
}
G.vexnum = i;
//初始化邻接矩阵
for(i = 0; i < G.vexnum; ++i){
for(j = 0; j < G.vexnum; ++j){
G.arcs[i][j] = 0;
}
}
//输入边信息
while(scanf("%d %d", &i, &j) && i != -1 && j != -1){
G.arcs[i][j] = 1;
G.arcs[j][i] = 1;
}
//输入起点
scanf("%d", &start_point);
//查找起点下标
i = LocateVex(G, start_point);
if(i >= 0){
DFS(G, i, path, &max_score);
//输出路径
for(i = 0; path[i] != -1; ++i){
printf("%d ", G.vexs[path[i]]);
}
printf("\n");
//输出最大积分
printf("%d", max_score);
}
return 0;
}
int DFS(AMGraph G, int v, int *path, int *max_score)
{
int w, i;
int sum_score = G.vexs[v];
visited[v]=1;
//将起点加入路径
path[0] = v;
for(w=0; w<G.vexnum; ++w)
if (G.arcs[v][w] && !visited[w]){
sum_score += DFS(G, w, path+1, max_score);
if(sum_score > *max_score){
*max_score = sum_score;
//将路径保存到path中
for(i = 1; path[i] != -1; ++i){
path[i] = -1;
}
for(i = 0; i < G.vexnum; ++i){
if(visited[i]){
path[i] = i;
}
}
}
}
visited[v]=0;
return sum_score;
}
```
相关推荐
![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)