洛谷P1294 高手去散步搜索

洛谷P1294 高手去散步
搜索
求一个图的最长路
从任意点出发任意点结束的最长路

dfs深搜枚举那个点是起点
其实正宗最长路在中间也要判一下最大
防止图中有负权边

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <iostream>
 9 using namespace std ; 
10 
11 const int maxn = 21,maxm = 51,inf = 1e9 ; 
12 int n,m,cnt,mx ; 
13 int head[maxn] ; 
14 bool visit[maxn] ; 
15 struct node{
16     int to,val,pre ; 
17 }e[maxm*2];
18 
19 inline int read() 
20 {
21     char ch = getchar() ; 
22     int x = 0 , f = 1 ; 
23     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 
24     while(ch>='0'&&ch<='9') { x = x*10+ch-48 ; ch = getchar() ; } 
25     return x * f ; 
26 }
27 
28 inline void add(int x,int y,int v) 
29 {
30     e[++cnt].to = y ; 
31     e[cnt].val = v ;
32     e[cnt].pre = head[x] ; 
33     head[x] = cnt ;  
34 }
35 
36 inline void dfs(int u,int sum) 
37 {
38     if(sum > mx) mx = sum ; 
39     int v ; 
40     visit[ u ] = 1 ;  
41     for(int i=head[u];i;i=e[ i ].pre) 
42     {
43         v = e[ i ].to ; 
44         if(!visit[ v ]) 
45             dfs(v,sum+e[ i ].val) ; 
46     }
47     visit[ u ] = 0 ; 
48 }
49 
50 int main() 
51 {
52     n = read() ;    m = read() ; 
53     int x,y,v ; 
54     mx = -inf ; 
55     for(int i=1;i<=m;i++) 
56     {
57         x = read() ; y = read() ; v = read() ; 
58         add(x,y,v) ;  add(y,x,v) ; 
59     } 
60     for(int i=1;i<=n;i++) 
61     {
62         for(int j=0;j<=n;j++) visit[ j ] = 0 ;     //   初始化一下 
63         dfs( i,0 ) ;  
64     }
65     printf("%d",mx) ; 
66     return 0 ; 
67 }

洛谷P1294 高手去散步 搜索

洛谷P1294 高手去散步搜索