做过相同类型的题
题意就是求树的直径,即树中任意两点之间带权路径和的最大值。
思路就是用两次BFS,第一次搜到直径的一端,第二次就直接计算直径的长度。至于为啥是这样,是有数学证明的,嗯……其实我没懂,我只是记住了两次BFS能找到直径╮(╯▽╰)╭
#include<iostream>
#include<queue>
#define N 10000
using namespace std;
typedef struct Edge {
int v;
int info;
struct Edge* next;
} Edge;
Edge head[N];
int n,sum;
int D[N];
bool visited[N];
queue<int> q;
int bfs_2() {
int _head=0,_tail=0;
q.push(1);
visited[1]=1;
while(!q.empty()) {
int v=q.front();
q.pop();
for(Edge* i=head[v].next; i; i=i->next) {
if(!visited[i->v]) {
D[i->v]=D[v]+(i->info);
q.push(i->v);
visited[i->v]=1;
}
}
}
fill(visited,visited+n+1,0);
int max=D[1],index=1;
for(int i=2; i<=n; i++)
if(max<D[i]) {
max=D[i];
index=i;
}
fill(D,D+n+1,0);//这里+1是因为是从1开始的
q.push(index);
visited[index]=1;
while(!q.empty()) {
int v=q.front();
q.pop();
for(Edge* i=head[v].next; i; i=i->next) {
if(!visited[i->v]) {
D[i->v]=D[v]+(i->info);
q.push(i->v);
visited[i->v]=1;
}
}
}
max=D[1],index=1;
for(int i=2; i<=n; i++)
if(max<D[i]) {
max=D[i];
index=i;
}
return max*10+(1+max)*max/2;
}
int main() {
cin>>n;
for(int i=0; i<n-1; i++) {
int x,y,data;
cin>>x>>y>>data;
Edge *tp1,*tp2;
tp1=new Edge;
tp2=new Edge;
tp1->info=tp2->info=data;
tp1->v=y;
tp1->next=head[x].next;
head[x].next=tp1;
tp2->v=x;
tp2->next=head[y].next;
head[y].next=tp2;
}
cout<<bfs_2();
return 0;
}