题解 P1099 【树网的核】

~~这么简单的题我竟然花了几个小时~~ # 看到数据规模就知道可以枚举暴力 方法： 先预处理任意两点距离。 再枚举可以成为树网的核的路径。 偏心距计算方法： ``` inline int find_f(int i,int j){ if(vis[i][j]!=0)return vis[i][j];//防止同一段算了很多次 int ma=0; for(int k=1;k<=n;k++){ ma=max(ma,(dist[i][k]+dist[j][k]-dist[i][j])/2); } return vis[i][j]=vis[j][i]=ma; }//以i，j为树网的核，找偏心距 ``` C++AC代码 ``` #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; inline int Read(){ int x=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x; }//读入优化 struct Node{ int v; int next; int val; }node[2020]; int dist[2020][2020]; int maxn; int vis[2010][2010],df[2010][2010]; int n,s,f; queue<int>q; int inque[1010]; int top,head[1010]; inline void addedge(int u,int v,int val){ node[++top].v=v; node[top].val=val; node[top].next=head[u]; head[u]=top; }//邻接表加边 inline int max(int a,int b){ return a>b?a:b; } inline int min(int a,int b){ return a<b?a:b; } void spfa(int st){ dist[st][st]=0; q.push(st); int u,i,d; while(!q.empty()){ u=q.front(); inque[u]=0; q.pop(); for(i=head[u];i;i=node[i].next){ d=node[i].v; if(dist[st][d]>dist[st][u]+node[i].val){ dist[st][d]=node[i].val+dist[st][u]; maxn=max(maxn,dist[st][d]); if(inque[d]==0){ q.push(d); inque[d]=1; } } } } }//spfa inline int find_f(int i,int j){ if(vis[i][j]!=0)return vis[i][j]; int ma=0; for(int k=1;k<=n;k++){ ma=max(ma,(dist[i][k]+dist[j][k]-dist[i][j])/2); } return vis[i][j]=vis[j][i]=ma; }//以i，j为树网的核，找偏心距 int dfs(int i,int j){ if(df[i][j]!=0)return df[i][j];//记忆化省时间 int mi=1<<30,k,d; mi=min(mi,find_f(i,i));//树网的核可以为单个点 mi=min(mi,find_f(j,j)); if(dist[i][j]<=s)mi=min(mi,find_f(i,j));//线段（i，j）可以成为树网的核 for(k=head[i];k;k=node[k].next){ d=node[k].v; if(dist[d][j]+dist[i][d]==dist[i][j]){//d在直径上 if(dist[d][j]<=s)mi=min(mi,find_f(d,j));//线段（d，j）可以为树网的核 mi=min(mi,dfs(d,j)); break;//肯定只有一个与i相连的点在这条直径上 } }//从i向j找树网的核 for(k=head[j];k;k=node[k].next){ d=node[k].v; if(dist[d][j]+dist[i][d]==dist[i][j]){ if(dist[i][d]<=s)mi=min(mi,find_f(i,d)); mi=min(mi,dfs(i,d)); break; } }//同上，从j向i走 return df[i][j]=df[j][i]=mi; }//i，j表示直径两端点 int main(){ memset(dist,0x3f3f3f3f,sizeof(dist)); n=Read(),s=Read(); f=1<<30; register int i,j; int a,b,val; for(i=1;i<n;i++){ a=Read(),b=Read(),val=Read(); addedge(a,b,val); addedge(b,a,val); } for(i=1;i<=n;i++)spfa(i);//得到任意两点距离 for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ if(dist[i][j]==maxn){//找直径 f=min(f,dfs(i,j));//求最小偏心距 } } } printf("%d",f); return 0; } ```