求助,思路是求树的重心,用bfs求最短路
查看原帖
求助,思路是求树的重心,用bfs求最短路
490694
Compound_Interest楼主2022/3/10 18:13
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=5e4+10;
vector<int> G[maxn];
int n,s[maxn],dp[maxn],ans;
bool vis[maxn];
queue<int> q;
void dfs(int root){
	s[root]=1;
	for(int i=0;i<G[root].size();i++){
		int v=G[root][i];
		if(vis[v]) continue;
		vis[v]=1;
		dfs(v);
		vis[v]=0;
		s[root]+=s[v];
		dp[root]=max(dp[root],s[v]);
	}
	dp[root]=max(dp[root],n-s[root]);
}

void geta(int u){
	int k=1,fir=u,t=-1;
	vis[u]=1;
	q.push(u);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		//printf("now=%d\n",now);	
		for(int i=0;i<G[now].size();i++){
			int v=G[now][i];
			if(vis[v]) continue;
		//		printf("v=%d k=%d\n",v,k);
			vis[v]=1;
			q.push(v);
			ans+=k;
			if(now==fir) t=v;
		}
	//	printf("now=%d x=%d\n",now,x);
		if(now==fir) now=t,k++;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	vis[1]=1;
	dfs(1);
	vis[1]=0;
//	puts("!!!");
	int mn=0x3f3f3f3f;
	for(int i=1;i<=n;i++) mn=min(mn,dp[i]);
	for(int i=1;i<=n;i++){
		if(dp[i]==mn){
		//	printf("i=%d\n",i);
			vis[i]=1;
			geta(i);
			printf("%d %d\n",i,ans);
			return 0;
		}
	}
	return 0;
}

bfs的思路是记录一个点更新层数,因为根到第k层的点的距离一样,bfs全wa,dfs可以ac

2022/3/10 18:13
加载中...