自动搬运

查看原文

来自洛谷，原作者为

	Diaоsi Enemy of God

搬运于2025-08-24 21:23:26，当前版本为作者最后更新于2019-09-14 00:03:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$Update:$更新于20191130，去掉了标题行，并不是重复题解，望通过

我是萌新，刚刚上手dfs

记得上周一在被柳州小学生神仙吊打的时候就是靠深搜苟了20分

这题思路很简单，我的做法是搜索+回溯

当无法达到下一层时（走到尽头或者所有点都被访问过）

就统计此时的最长路，然后更新答案

回溯时就将长度减去，然后搜索下一个点

dfs代码：

void dfs(int st){//深度优先搜索 
	for(int i=1;i<=n;i++){
		if(g[st][i]&&!vis[i]){
			vis[i]=1;
			dist+=g[st][i];
			dfs(i);
			dist-=g[st][i];//回溯 
		}
	}
	max_d=max(max_d,dist);//统计最大深度 
	vis[st]=0;
	return;
}

在主函数中依次以每个点为起点进行深度优先搜索

for(int i=1;i<=n;i++){
    vis[i]=1;
    dfs(i);
    memset(vis,0,sizeof(vis));//记得清空标记数组
}

最后，完整代码奉上：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],dist,max_d=-10*N,n,m;
bool vis[N];
void dfs(int st){//深度优先搜索 
	for(int i=1;i<=n;i++){
		if(g[st][i]&&!vis[i]){
			vis[i]=1;
			dist+=g[st][i];
			dfs(i);
			dist-=g[st][i];//回溯 
		}
	}
	max_d=max(max_d,dist);//统计最大深度 
	vis[st]=0;
	return;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;//读入边和对应的权值 
		g[x][y]=z;
		g[y][x]=z;
	}
	for(int i=1;i<=n;i++){
        vis[i]=1;
        dfs(i);
        memset(vis,0,sizeof(vis));//记得清空标记数组
    }
    cout<<max_d;
	return 0;
}

萌新发题解求过，如果有问题可以在评论区指出