AC了,但是问个问题
查看原帖
AC了,但是问个问题
768612
Iniaugoty楼主2023/6/27 21:08

为什么深进和置顶题解,在我注释的一行(即求直径的第一次dfs)前,都加了 dis[1]=1 啊?感觉好像没什么区别,请问有什么意义吗?

#include<bits/stdc++.h>
#define N 303
using namespace std;
int n,s,ans=2e9,far;
int dis[N],fa[N];
bool flag[N];
int head[N],cnt;
struct star{
	int next,to,val;
}e[N<<1];
void add(int u,int v,int w){
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].val=w;
	head[u]=cnt;
}
void dfs(int u,int f){
	fa[u]=f;
	if(dis[u]>dis[far]) far=u;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to,w=e[i].val;
		if(v==f||flag[v]) continue;
		dis[v]=dis[u]+w,dfs(v,u);
	}
}
signed main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>s;
	for(int i=1,u,v,w;i<n;i++)
		cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	int a,b;
	//dfs(1,0),a=far;
	dis[a]=0,dfs(a,0),b=far;
	for(int i=b,j=b;i;i=fa[i]){
		while(dis[j]-dis[i]>s) j=fa[j];
		ans=min(ans,max(dis[b]-dis[j],dis[i]));
	}
	for(int i=b;i;i=fa[i]) flag[i]=1;
	for(int i=b;i;i=fa[i])
		dis[i]=0,dfs(i,fa[i]);
	for(int i=1;i<=n;i++)
		ans=max(ans,dis[i]);
	cout<<ans;
	return 0;
}

(应该不难理解这些变量的意思吧)

2023/6/27 21:08
加载中...