高手最近谈恋爱了。不过是单相思。“即使是单相思，也是完整的爱情”，高手从未放弃对它的追求。今天，这个阳光明媚的早晨，太阳从西边缓缓升起。于是它找到高手，希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会，他已经准备好了一切。
鳌头山上有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，保证观景点两两之间不会有多条游步道连接.
欲求数的直径，结果绕起圈圈了、、
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 110 using namespace std; bool vis[N],vist[N]; int n,m,x,y,z,ans,tot,root,fa[N],dis[N],head[N]; int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } struct Edge { int to,dis,next,from; }edge[N]; int add(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].next=head[x]; head[x]=tot; } int dfs(int x) { vist[x]=true; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(vis[to]||fa[x]==to) continue; vis[to]=true;fa[to]=x; dis[to]=dis[x]+edge[i].dis; dfs(to); vis[to]=false; } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } for(int i=1;i<=n;i++) { if(vist[i]) continue; memset(dis,0,sizeof(dis)); dfs(i);root=i; for(int i=1;i<=n;i++) if(dis[i]>dis[root]) root=i; memset(dis,0,sizeof(dis)); dfs(root); for(int i=1;i<=n;i++) if(ans<dis[i]) ans=dis[i]; } printf("%d",ans); return 0; }
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 110 using namespace std; bool vis[N]; int n,m,x,y,z,ans,tot,head[N]; int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } struct Edge { int to,dis,next,from; }edge[N]; int add(int x,int y,int z) { tot++; edge[tot].to=y; edge[tot].dis=z; edge[tot].next=head[x]; head[x]=tot; } int dfs(int x) { if(vis[x]) return 0; vis[x]=true; int sum=0; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(!vis[to]) sum=max(sum,dfs(to)+edge[i].dis); } vis[x]=false; return sum; } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } for(int i=1;i<=n;i++) { if(vis[i]) continue; ans=max(ans,dfs(i)); } printf("%d",ans); return 0; }
纵使知道会一败涂地，纵使知道结果会不尽人意，我仍然选择倾尽全力，直到被伤的体无完肤，只图无怨无悔
原文：http://www.cnblogs.com/z360/p/7582803.html
