【BZOJ4016】[FJOI2014]最短路径树问题

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#include <utility>#include <vector>#include <algorithm>#define mp(A,B)	make_pair(A,B)#define fir(_) ((_).first)#define sec(_) ((_).second)using namespace std;typedef pair<int,int> pii;const int maxn=30010;const int inf=0x3f3f3f3f;int n,m,K,cnt,root,tot,maxx,ans,sum,d;int to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],dis[maxn],vis[maxn],dep[maxn];int fl[maxn],fs[maxn],gl[maxn],gs[maxn],siz[maxn];vector<pii> e[maxn];priority_queue<pii> pq;void add(int a,int b,int c){	//printf("%d %d %d\n",a,b,c);	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;}void dijkstra(){	memset(dis,0x3f,sizeof(dis));	dis[1]=0;	int i,u;	pii y;	pq.push(mp(0,-1));	while(!pq.empty())	{		u=-sec(pq.top()),pq.pop();		if(vis[u])	continue ;		vis[u]=1;		for(int i=0;i<e[u].size();i++)		{			y=e[u][i];			if(dis[fir(y)]>dis[u]+sec(y))				dis[fir(y)]=dis[u]+sec(y),pq.push(mp(-dis[fir(y)],-fir(y)));		}	}	memset(vis,0,sizeof(vis));}void Dfs(int x){	vis[x]=1;	for(int i=0;i<e[x].size();i++)	{		pii y=e[x][i];		if(!vis[fir(y)]&&dis[fir(y)]==dis[x]+sec(y))			Dfs(fir(y)),add(x,fir(y),sec(y)),add(fir(y),x,sec(y));	}}void getr(int x,int fa){	siz[x]=1;	int i,mx=0;	for(i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]]||to[i]==fa)	continue;		getr(to[i],x),siz[x]+=siz[to[i]];		mx=max(mx,siz[to[i]]);	}	if(maxx>max(tot-siz[x],mx))	maxx=max(tot-siz[x],mx),root=x;}void getd(int x,int fa,int dep,int len){	if(dep>=K)	return ;	d=max(d,dep);	if(gl[dep]<len)	gl[dep]=len,gs[dep]=0;	if(gl[dep]==len)	gs[dep]++;	for(int i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]]||to[i]==fa)	continue;		getd(to[i],x,dep+1,len+val[i]);	}}void dfs(int x){	vis[x]=1;	int i,j,dd=0;	fs[0]=1;	for(i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]])	continue;		d=0,getd(to[i],x,1,val[i]),dd=max(dd,d);		for(j=1;j<=d;j++)		{			if(ans<fl[K-j-1]+gl[j])	ans=fl[K-j-1]+gl[j],sum=0;			if(ans==fl[K-j-1]+gl[j])	sum+=fs[K-j-1]*gs[j];		}		for(j=1;j<=d;j++)		{			if(fl[j]<gl[j])	fl[j]=gl[j],fs[j]=0;			if(fl[j]==gl[j])	fs[j]+=gs[j];			gl[j]=-inf,gs[j]=0;		}	}	for(i=1;i<=dd;i++)	fl[i]=-inf,fs[i]=0;	for(i=head[x];i!=-1;i=next[i])	{		if(vis[to[i]])	continue;		tot=siz[to[i]],maxx=1<<30,getr(to[i],x),dfs(root);	}}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int main(){	//freopen("bz4016.in","r",stdin);	//freopen("bz4016.out","w",stdout);	n=rd(),m=rd(),K=rd();	int i,a,b,c;	for(i=1;i<=m;i++)	a=rd(),b=rd(),c=rd(),e[a].push_back(mp(b,c)),e[b].push_back(mp(a,c));	for(i=1;i<=n;i++)	sort(e[i].begin(),e[i].end());	memset(head,-1,sizeof(head));	dijkstra(),Dfs(1);	memset(vis,0,sizeof(vis));	for(i=1;i<=n;i++)	fl[i]=gl[i]=-inf;	tot=n,maxx=1<<30,getr(1,0),dfs(root);	printf("%d %d",ans,sum);	return 0;}