P1294 高手去散步

題目背景

高手最近談戀愛了。不過是單相思。“即使是單相思，也是完整的愛情”，高手從未放棄對它的追求。今天，這個陽光明媚的早晨，太陽從西邊緩緩升起。於是它找到高手，希望在晨讀開始之前和高手一起在鰲頭山上一起散步。高手當然不會放棄這次夢寐以求的機會，他已經準備好了一切。

題目描述

鰲頭山上有n個觀景點，觀景點兩兩之間有游步道共m條。高手的那個它，不喜歡太刺激的過程，因此那些沒有路的觀景點高手是不會選擇去的。另外，她也不喜歡去同一個觀景點一次以上。而高手想讓他們在一起的路程最長（觀景時它不會理高手），已知高手的穿梭機可以讓他們在任意一個觀景點出發，也在任意一個觀景點結束。

輸入輸出格式

第一行，兩個用空格隔開的整數n、m. 之後m行，為每條游步道的信息：兩端觀景點編號、長度。

一個整數，表示他們最長相伴的路程。

輸入輸出樣例

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

150

說明

對於100%的數據:n≤20，m≤50，保證觀景點兩兩之間不會有多條游步道連接.

dfs暴力！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 void read(int & n)
 7 {
 8     char c='+';int x=0;bool flag=0;
 9     while(c<'0'||c>'9')
10     {
11         c=getchar();
12         if(c=='-')flag=1;    
13     }
14     while(c>='0'&&c<='9')
15         x=x*10+c-48,c=getchar();
16     flag==1?n=-x:n=x;
17 }
18 const int MAXN=100001;
19 struct node
20 {
21     int u,v,w,nxt;
22 }edge[MAXN];
23 int head[MAXN];
24 int num=1;
25 int n,m;
26 int vis[MAXN];
27 int ans=0;
28 void add_edge(int x,int y,int z)
29 {
30     edge[num].u=x;
31     edge[num].v=y;
32     edge[num].w=z;
33     edge[num].nxt=head[x];
34     head[x]=num++;
35 }
36 void dfs(int p,int now)
37 {
38     ans=max(ans,now);
39     vis[p]=1;
40     for(int i=head[p];i!=-1;i=edge[i].nxt)
41         if(vis[edge[i].v]==0)
42             dfs(edge[i].v,now+edge[i].w);
43     vis[p]=0;
44 }
45 int main()
46 {
47     read(n);read(m);
48     for(int i=1;i<=n;i++)head[i]=-1;
49     for(int i=1;i<=m;i++)
50     {
51         int x,y,z;
52         read(x);read(y);read(z);
53         add_edge(x,y,z);
54         add_edge(y,x,z);
55     }
56     for(int i=1;i<=n;i++)
57     {
58         memset(vis,0,sizeof(vis));
59         dfs(i,0);
60     }
61     printf("%d",ans);
62     return 0;
63 }