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;
int n;
int s;
int maxn;
int fa;
bool flag;
bool vis;
int ans=0x7fffffff;
vector<int>G;
int tot;
inline void Floyd()
{
for(int i=1;i<=n;i++)
f=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
f=min(f+f,f);
}
inline void dfs(int x,int goal,int fat)
{
if(x==goal)
{
flag=true;
fa=fat;
return;
}
int siz=G.size();
for(int i=0;i<siz;i++)
{
int go=G;
if(go!=fat)
dfs(go,goal,x);
if(flag)
{
fa=fat;
return;
}
}
}
inline void dfss(int x,int dis,int fa)
{
tot=max(tot,dis);
if(dis>=ans) return;
int siz=G.size();
for(int i=0;i<siz;i++)
{
int go=G;
if(!vis&&go!=fa)
dfss(go,dis+f,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=true;
int dis=0;
while(1314520)
{
if(!fa) break;
if(dis+f]>s) break;
dis+=f];
end=fa;
vis=true;
}
if(start==end)
{
for(int i=1;i<=n;i++)
tot=max(tot,f);
}
else
{
int teme=start;
while(teme)
{
dfss(teme,0,0);
if(teme==end) break;
teme=fa;
}
}
ans=min(ans,tot);
start=fa;
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=f=c;
G.push_back(b);
G.push_back(a);
}
Floyd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
maxn=max(maxn,f);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(f==maxn)
cl(i,j);
cout<<ans<<endl;olinr love_nmr;
}
----olinr
文档来源：51CTO技术博客https://blog.51cto.com/u_15314204/3190981
页:
[1]