NOIP 提高 2011 第一轮 第 25 题：DFS 枚举求图中最长路径

题目

```
#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
    int i;
    visited[x]= true;
    if(len>ans)
       ans=len;
    for(i=1;i<=n;i++)
       if( (!visited[i]) && (e[x][i]!=-1) )
          dfs(i,len+e[x][i]);
    visited[x]=false;
}
int main()
{
    int i,j,a,b,c;
    cin>>n>>m;
    for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
          e[i][j]=-1;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        e[a][b]=c;
        e[b][a]=c;
    }
    for(i=1;i<=n;i++)
       visited[i]=false;
    ans=0;
    for(i=1;i<=n;i++)
       dfs(i,0);
    cout<<ans<<endl;
    return 0;
}
```
输入：  
4 6  
1 2 10  
2 3 20  
3 4 30  
4 1 40  
1 3 50  
2 4 60    
输出：______________

请写出程序的输出结果。

答案

150

题解

考点定位

本题考「DFS 最长路径模拟」,对应大纲 4.3.3 搜索（难度【3】）。

解题过程

程序对每个起点 DFS 枚举所有简单路径，ans 记录最长路径长度。输入（原卷）：n=4? 图 4 点 6 边：1-2=10,2-3=20,3-4=30,4-1=40,1-3=50,2-4=60。全枚举：任意两点的直接边与绕行路径，最长 = 大边 60 + 相连……路径 1-4(40)-2(60)-3(20) = 120；4-1(40)-3(50)-2(20)=110；3-2(20)-4(60)-1(40)=120；2-3(20)-1(50)-4(40)=110。最长 120。

答案：120。

易错提醒

① visited 回溯使每个简单路径都被枚举；② visited[x]=false 在返回前恢复——这是枚举全部路径的关键（与普通 DFS 遍历不同）。