[NOIP2007] 树网的核

关键在于读题

知道要求的东西后，直接建立数据结构直接暴力即可

时间复杂度 \(O(n^3)\)

#include<bits/stdc++.h>
using namespace std;
const int N=302;

int n,s;
vector<int> e[N],p[N];//next path

int pre[N];// 找直径时的前驱
int dpre[N]={0};// 到达直径一端的路径长度
int bfs(int s){// 找距离最远的点，用于求直径
    int d[N]={0};
    bool bfs_vis[N]={0};
    queue <int> q;
    memset(pre,0,sizeof(pre));
    q.push(s),bfs_vis[s]=true;
    while(!q.empty()){
        int k=q.front();q.pop();
        for(int i=0;i<e[k].size();i++){
            const int &j=e[k][i],&v=p[k][i];
            if(bfs_vis[j])continue;
            q.push(j),bfs_vis[j]=true,d[j]=d[k]+v,pre[j]=k;// 标记前驱
        }
    }
    int res,mx=0;
    for(int i=1;i<=n;i++){
        if(d[i]>mx)mx=d[i],res=i;
        dpre[i]=d[i];
    }
    return res;
}
int ecc(int s,int t){// 找最小偏心距
    int d[N]={0};// 到达该点的路径长度
    bool bfs_vis[N]={0};
    queue <int> q;
    for(int i=t;i!=pre[s];i=pre[i])q.push(i),bfs_vis[i]=true;
    while(!q.empty()){
        int k=q.front();q.pop();
        for(int i=0;i<e[k].size();i++){
            const int &j=e[k][i],&v=p[k][i];
            if(bfs_vis[j])continue;
            d[j]=d[k]+v,q.push(j),bfs_vis[j]=true;
        }
    }
    int mx=0;
    for(int i=1;i<=n;i++)if(d[i]>mx)mx=d[i];
    return mx;
}

int main(){
    scanf("%d%d",&n,&s);
    for(int i=1;i<n;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[a].push_back(b);p[a].push_back(c);
        e[b].push_back(a);p[b].push_back(c);
    }
    int l=bfs(1),r=bfs(l);
    int ans=0x3f3f3f3f;
    for(int i=r;i;i=pre[i])for(int j=i;j;j=pre[j]){
        if(dpre[i]-dpre[j]<=s)ans=min(ans,ecc(j,i));
        else break;
    }
    printf("%d",ans);
    return 0;
}

[NOIP2007] 树网的核

原文：https://www.cnblogs.com/sshwy/p/11026367.html