求助紫题
  • 板块灌水区
  • 楼主TainityAnle
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/10 18:01
  • 上次更新2023/10/28 06:54:54
查看原帖
求助紫题
550317
TainityAnle楼主2022/3/10 18:01

P3304 [SDOI2013]直径求助啊,3,4点WA,求大佬帮忙

代码:

#include<iostream> 
#include<string>
#include<cstdio>
using namespace std;
struct ds{
	int to,nxt,cnt,w;
}edge[400005];
int head[200005],cnt=1,n,x,y,ww,st,ks,ans,maxn;
long long maxx;
void add(int u,int v,int ww){
	edge[cnt].to=v;
	edge[cnt].nxt=head[u];
	edge[cnt].w=ww;
	head[u]=cnt++;
}
void dfs(int t,int die,long long dis){
	if(dis>maxx){
		maxx=dis;
		st=t;
	}
	for(int i=head[t];i;i=edge[i].nxt){
		int er=edge[i].to;
		if(er==die) continue;
		dfs(er,t,dis+edge[i].w);
	}
}
int dfs1(int t,int die,long long dis){
	if(dis==maxx) return 1;
	int flag=0;
	for(int i=head[t];i;i=edge[i].nxt){
		int er=edge[i].to;
		if(er==die) continue;
		int tmp=dfs1(er,t,dis+edge[i].w);
		if(tmp){
			edge[i].cnt+=tmp;
			if(edge[i].cnt>maxn){
				maxn=edge[i].cnt;
				ans=1;
			}else if(edge[i].cnt==maxn) ans++;
			flag+=tmp;
		}
	}
	return flag;
}
int main (){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>x>>y>>ww;
		add(x,y,ww);
		add(y,x,ww);
	}
	dfs(1,0,0);
	ks=st;
	dfs(ks,0,0);
	cout<<maxx;
	dfs1(ks,0,0);
	cout<<endl<<ans-1;
	return 0;
}
2022/3/10 18:01
加载中...