1.求树的直径
#include<stdio.h> #include<string.h> #include<queue> #define MAX 100000 using namespace std; int head[MAX]; int vis[MAX];//标记当前节点是否已经用过 int dis[MAX];//记录最长距离 int n,m,ans; int sum;//记录最长路径的长度 int aga; struct node { int u,v,w; int next; }edge[MAX]; void add(int u,int v,int w)//向邻接表中加边 { edge[ans].u=u; edge[ans].v=v; edge[ans].w=w; edge[ans].next=head[u]; head[u]=ans++; } void getmap() { int i,j; int a,b,c; ans=0; memset(head,-1,sizeof(head)); while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } } void bfs(int beg) { queue<int>q; memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); int i,j; while(!q.empty()) q.pop(); aga=beg; sum=0; vis[beg]=1; q.push(beg); int top; while(!q.empty()) { top=q.front(); q.pop(); for(i=head[top];i!=-1;i=edge[i].next) { if(!vis[edge[i].v]) { dis[edge[i].v]=dis[top]+edge[i].w; vis[edge[i].v]=1; q.push(edge[i].v); if(sum<dis[edge[i].v]) { sum=dis[edge[i].v]; aga=edge[i].v; } } } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { getmap(); bfs(1);//搜索最长路径的一个端点 bfs(aga);//搜索另一个端点 printf("%d\n",sum); } return 0; }