题目大意
给定一个无向图,这个无向图满足其为一棵树,求树的直径的最大值
解题思路
随便找一个点进行bfs,找到距离这个点最远的点。用这个最远的点作为起点,进行bfs,此时找到最远点距离起点的值,即为直径。
代码实现
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 4e4+7;
int T;
int n,m;
int vis[N],dis[N];
struct Edge{
int to,v;
};
vector<Edge> v[N];
queue<int> q;
void bfs(int st){
for(int i = 1; i <= n; i++) vis[i] = 0;
for(int i = 1; i <= n; i++) dis[i] = inf;
while(!q.empty()) q.pop();
q.push(st);
vis[st] = 1;
dis[st] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
int sz = v[u].size();
Edge uu;
for(int i = 0 ; i < sz; i++) { //for(auto i : v[u])
uu=v[u][i];
if(!vis[uu.to]) {
vis[uu.to] = 1;
dis[uu.to] = min(dis[u] + uu.v , dis[uu.to]);
q.push(uu.to);
}
}
}
}
int main(){
cin>>n>>m;
char no_use_;
int from_, to_, v_;
Edge qwq;
for(int i = 1 ; i <= m ; i++) {
scanf("%d %d %d %c",&from_,&to_,&v_,&no_use_);
qwq.to=to_,qwq.v=v_;
v[from_].push_back(qwq);
qwq.to=from_,qwq.v=v_;
v[to_].push_back(qwq);
}
bfs(1);
int ww;
int max_len = 0;
for(int i = 1; i <= n; i++) {
if(dis[i] > max_len) {
max_len = dis[i];
ww = i;
}
}
bfs(ww);
max_len = 0;
for(int i = 1; i <= n; i++) {
if(dis[i] > max_len) {
max_len = dis[i];
}
}
cout<<max_len<<endl;
return 0;
}
0 条评论