题解 P1294 【高手去散步】
Diaоsi
·
·
题解
------------
我是萌新，刚刚上手dfs
~~记得上周一在被柳州小学生神仙吊打的时候就是靠深搜苟了20分~~
这题思路很简单，我的做法是搜索+回溯
当无法达到下一层时（走到尽头或者所有点都被访问过）
就统计此时的最长路，然后更新答案
回溯时就将长度减去，然后搜索下一个点
### dfs代码：
```cpp
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;
}
```
### 在主函数中依次以每个点为起点进行深度优先搜索
```cpp
for(int i=1;i<=n;i++){
vis[i]=1;
dfs(i);
memset(vis,0,sizeof(vis));//记得清空标记数组
}
```
### 最后，完整代码奉上：
```cpp
#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;
}
```
## 萌新发题解求过，如果有问题可以在评论区指出