萌新求助点分治
查看原帖
萌新求助点分治
35754
whiteqwq楼主2020/8/22 10:48

感觉在找重心的时候错了,然后改了一下求重心的函数,却TLE了,求助大佬为什么是这样:

原来的findfind

void find(int x,int tot){
	int maxx=0;
	size[x]=1,fvis[x]=stp;
	for(int i=start[x];i;i=then[i]){
		int y=to[i];
		if(fvis[y]==stp||fin[y])
			continue;
		find(y,tot);
		size[x]+=size[y];
		maxx=max(maxx,size[y]);
	}
	maxx=max(maxx,tot-size[x]);
	if(maxx<minn)
		minn=maxx,pos=x;
}

stp++,minn=inf,find(x,sum);

更改后的findfind

void find(int x){
	int maxx=0;
	size[x]=1,fvis[x]=stp,tmp++;
	for(int i=start[x];i;i=then[i]){
		int y=to[i];
		if(fvis[y]==stp||fin[y])
			continue;
		find(y);
		size[x]+=size[y];
		maxx=max(maxx,size[y]);
	}
	maxx=max(maxx,tmp-size[x]);
	if(maxx<minn)
		minn=maxx,pos=x;
}

stp++,minn=inf,tmp=0,find(x);

给出hack第一个findfind的数据

1 2
1 3
2 4
2 5
3 6
3 7
3 8

此时找到的第一个重心为33,遍历到11后由于size1=8size_1=8,所以会将重心错选为11

2020/8/22 10:48
加载中...