一个问题
  • 板块题目总版
  • 楼主Alea
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/3 21:30
  • 上次更新2023/10/23 13:57:01
查看原帖
一个问题
322792
Alea楼主2023/6/3 21:30

我的求树的直径出现了问题,蒟蒻求调!

#include <iostream>
#include <vector>
using namespace std;
const int size=10010;
int n,f[2][size],ans;
vector<pair<int,int>> edgs[size];
void dfs(int fa,int u){
    f[0][u]=f[1][u]=0; //longest and second-longest
    for(auto edg:edgs[u]){
        int v=edg.first;
        if(v!=fa) dfs(u,v);
    }
    for(auto edg:edgs[u]){
        int v=edg.first,w=edg.second;
        if(f[0][v]+w>f[0][u]) f[1][u]=f[0][u],f[0][u]=f[0][v]+w;
        else if(f[0][v]+w>f[1][u]) f[1][u]=f[0][v]+w;
    }
    ans=max(ans,f[0][u]+f[1][u]);
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        edgs[u].push_back(make_pair(v,w));
        edgs[v].push_back(make_pair(u,w));
    }
    dfs(0,1);
    cout<<ans<<endl;
    return 0;
}
2023/6/3 21:30
加载中...