首页 > 代码库 > 【BZOJ4016】[FJOI2014]最短路径树问题 最短路径树+点分治

【BZOJ4016】[FJOI2014]最短路径树问题 最短路径树+点分治

2024-10-10 21:43:02   221人阅读

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

Description

给一个包含n个点，m条边的无向连通图。从顶点1出发，往其余所有点分别走一次并返回。
往某一个点走时，选择总长度最短的路径走。若有多条长度最短的路径，则选择经过的顶点序列字典序最小的那条路径(如路径A为1,32,11，路径B为1,3,2,11，路径B字典序较小。注意是序列的字典序的最小，而非路径中节点编号相连的字符串字典序最小)。到达该点后按原路返回，然后往其他点走，直到所有点都走过。
可以知道，经过的边会构成一棵最短路径树。请问，在这棵最短路径树上，最长的包含K个点的简单路径长度为多长？长度为该最长长度的不同路径有多少条？
这里的简单路径是指：对于一个点最多只经过一次的路径。不同路径是指路径两端端点至少有一个不同，点A到点B的路径和点B到点A视为同一条路径。

Input

第一行输入三个正整数n,m，K，表示有n个点m条边，要求的路径需要经过K个点。接下来输入m行，每行三个正整数Ai,Bi,Ci(1<=Ai,Bi<=n,1<=Ci<=10000)，表示Ai和Bi间有一条长度为Ci的边。数据保证输入的是连通的无向图。

Output

输出一行两个整数，以一个空格隔开，第一个整数表示包含K个点的路径最长为多长，第二个整数表示这样的不同的最长路径有多少条。

Sample Input

6 6 4
1 2 1
2 3 1
3 4 1
2 5 1
3 6 1
5 6 1

Sample Output

3 4

HINT

对于所有数据n<=30000,m<=60000，2<=K<=n。
数据保证最短路径树上至少存在一条长度为K的路径。
2016.12.7新加数据一组by - wyxxqz-150137

题解：做这种题总有一种奇怪的违和感，感觉就是强行把两道题拼起来变成一道题考~

子任务1：求最短路径树，这个直接Dijkstra+DFS就好，DFS时先走编号小的点。

子任务2：求树上包含k个点的最长路径的长度及条数，这个显然点分治。在以x为分治中心时，我们依次遍历它的所有儿子的子树，用fl[i]表示在之前的子树中，包含i个点的链的最长路径长度，用fs[i]表示条数；用gl[i]表示在当前的子树中，包含i个点的链的最长路径长度，用gs[i]表示条数，然后搞一搞就行了。

#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;}

【BZOJ4016】[FJOI2014]最短路径树问题 最短路径树+点分治


联系
我们