P1099 树网的核

上山打老虎

woc，这题就这么A了？（不敢相信）
题意：定义树核为树上最长链上的一段（长度不超过s）（也可以是一个点）
定义偏心距为到树核最远的距离，求最小偏心距
woc纯暴力居然过了
Floyd+爆搜
先找到最长链（可能不只一条）
枚举起点终点，暴力找最远距离
一遍过666
n<=300

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;#define olinr return#define love_nmr 0
int f[350][350];
int n;
int s;
int maxn;
int fa[350];
bool flag;
bool vis[350];
int ans=0x7fffffff;
vector<int>G[350];
int tot;
inline void Floyd()
{
  for(int i=1;i<=n;i++)
    f[i][i]=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)  
      for(int k=1;k<=n;k++)
        f[j][k]=min(f[j][i]+f[i][k],f[j][k]);
}
inline void dfs(int x,int goal,int fat)
{
  if(x==goal)
  {
    flag=true;
    fa[x]=fat;
    return;
  }
  int siz=G[x].size();
  for(int i=0;i<siz;i++)
  {
    int go=G[x][i];
    if(go!=fat)
      dfs(go,goal,x);
    if(flag)
    {
      fa[x]=fat;
      return;
    }
  }
}
inline void dfss(int x,int dis,int fa)
{
  tot=max(tot,dis);
  if(dis>=ans) return;
  int siz=G[x].size();
  for(int i=0;i<siz;i++)
  {
    int go=G[x][i];
    if(!vis[go]&&go!=fa)
      dfss(go,dis+f[x][go],x);
  }
}
inline void cl(int x,int y)
{
  memset(fa,0,sizeof fa);
  flag=0;
  dfs(x,y,0);
  int start=y;
  while(5201314)
  {   
    tot=0;
    memset(vis,0,sizeof vis);
    int end=start;
    vis[end]=true;
    int dis=0;
    while(1314520)
    {   
      if(!fa[end]) break;
      if(dis+f[end][fa[end]]>s) break;
      dis+=f[end][fa[end]];
      end=fa[end];
      vis[end]=true;
    }
    if(start==end)
    {
      for(int i=1;i<=n;i++)
        tot=max(tot,f[end][i]);
    }
    else
    {
      int teme=start;
      while(teme)
      {
        dfss(teme,0,0);
        if(teme==end) break;
        teme=fa[teme];  
      }
    }
    ans=min(ans,tot);
    start=fa[start];
    if(!start)break;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin>>n>>s;
  memset(f,0x3f,sizeof f);
  for(int a,b,c,i=1;i<n;i++)
  {
    cin>>a>>b>>c;
    f[a][b]=f[b][a]=c;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  Floyd();
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      maxn=max(maxn,f[i][j]);
  for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
      if(f[i][j]==maxn)
        cl(i,j);
  cout<<ans<<endl;olinr love_nmr;
}

----olinr