求助,简单代码为什么会死循环
  • 板块学术版
  • 楼主变成一名fw
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/5/22 21:25
  • 上次更新2023/11/7 02:00:36
查看原帖
求助,简单代码为什么会死循环
61121
变成一名fw楼主2020/5/22 21:25

在做树的重心模板,然后输入的时候死循环了,发现是

	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		es[x].push_back(y);
		es[y].push_back(x);

这里的问题,这样写不对吗

求助/kel

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,p[MAXN],sz[MAXN],f[MAXN],g[MAXN];
//p[i]记录i的父亲,sz[i]记录以i为根的子树大小 f[i]表示儿子为根的最大子树的大小,g[i]是删除i后最大分支的大小
vector < vector <int> > es;
void dfs(int u,int fa){//通过dfs求sz[],p[] 
	p[u]=fa;//初始化 
	sz[u]=1;//初始化 
	for(int i=0;i<es[u].size();i++){
		int v=es[u][i];     //找一个与之联通的点(子节点) 
		if(v==fa) continue; //排除掉v是父亲节点的情况 
		dfs(v,u);
		sz[u]+=sz[v];		//加上子节点的子树数量 
	}
} 
int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		es[x].push_back(y);
		es[y].push_back(x);
	} 
	//输入
	dfs(1,0);
	//求得sz和p
	for(int u=1;u<=n;u++){
		for(int i=0;i<es[u].size();i++){
			int v=es[u][i];
			if(v==p[u]) continue; //排除父亲节点的可能
			f[u]=max(f[u],sz[v]); //计算u儿子为根的最大子树的的大小 
		}
	} 
	for(int u=1;u<=n;u++){
		g[u]=max(f[u],n-sz[u]);//g[u]由两部分的最大值取得:以u的儿子们形成的区块,u的长辈们组成的区块 
	}
	
	int id=min_element(g+1,g+1+n)-g;//找到最小的g 
	cout<<id<<" "<<g[id]<<endl; 
 	return 0;
}

2020/5/22 21:25
加载中...