洛谷P1294 高手去散步

搜索

求一个图的最长路

从任意点出发 任意点结束的最长路

dfs深搜 枚举 那个点是起点

其实正宗最长路 在中间也要判一下最大

防止图中有负权边

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              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 }