请问第2,9,10个点怎么过
  • 板块P1395 会议
  • 楼主Cartier
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/4 16:41
  • 上次更新2024/8/4 18:21:28
查看原帖
请问第2,9,10个点怎么过
856898
Cartier楼主2024/8/4 16:41
#include<bits/stdc++.h>
using namespace std;
const int N=50006;
const int M=100006;
int h[N];
int e[N];
int ne[N];
int idx;
bool st[N];
void add(int a,int b){
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
	idx++;
}
int sum;//总和 
int n;//n个村民 
void dfs(int a,int dis){
for(int i=h[a];i!=-1;i=ne[i]){
	int f=e[i];
	if(!st[f]){
		st[f]=true;
		sum=sum+dis+1;
		dfs(f,dis+1);
	}
}

}
int main(){
	memset(h,-1,sizeof h);
	cin>>n;
	int a,b;
int p=n-1;
	while(p--){
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	st[1]=true;
	
	dfs(1,0);
	
	int ans=sum;
	int ansi=1;
	for(int i=2;i<=n;i++){
		memset(st,false,sizeof st);
		st[i]=true;
		int j=sum;
		sum=0;
		dfs(i,0);
		if(sum<ans){
			ans=sum;
			ansi=i;
		}
		
	}
	cout<<ansi<<" "<<ans;
	return 0;
}
2024/8/4 16:41
加载中...