首页 > 代码库 > 【bzoj4016】[FJOI2014]最短路径树问题 堆优化Dijkstra+DFS树+树的点分治

【bzoj4016】[FJOI2014]最短路径树问题 堆优化Dijkstra+DFS树+树的点分治

题目描述

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

输入

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

输出

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

样例输入

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

样例输出

3 4


题解

堆优化Dijkstra+DFS树+树的点分治

我会说本题难点在于求最短路径树吗?

首先题意理解了半天,还是不懂“而非路径中节点编号相连的字符串字典序最小”是啥意思,后来才发现还有这种非人类理解方法...

求题目要求的最短路径树方法:先求出最短路图(由所有构成最短路的边构成的图,对字典序没有要求),然后按照字典序求出最短路图的DFS树即为最短路径树。

证明:最短路径树一定在最短路图上,而修改字典序优先DFS树的任意一条边都会使字典序增大,因此命题得证

求出最短路径树之后就是点分治的问题了。

由于本题的点分治是固定点数的(即固定边数),因此可以直接开数组记录一下某深度的最大权值,然后使用类似于树形dp的方法来求答案。

具体地,设f[i]为当前子树深度为i的最大边权和,g[i]为之前子树以及根节点深度为i的最大边权和,那么对答案的贡献即为f[i]+g[k-1-i]。

可以证明时间复杂度最坏情况下是$O(n\log n)$的。

另外注意清空数组时不能使用memset,否则时间复杂度直接起飞。

数组多的不忍直视= =

#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <utility>#include <vector>#define N 30010#define inf 0x3fffffffusing namespace std;priority_queue<pair<int , int> > q;vector<int> v[N];int hh[N] , tt[N << 2]  , ll[N << 2] , nn[N << 2] , cc = 1 , vv[N] , dd[N] , uu[N];int n , k , head[N] , to[N << 1] , len[N << 1] , next[N << 1] , cnt;int vis[N] , root , sum , si[N] , bs[N] , f[N] , g[N] , sf[N] , sg[N] , md , deep[N] , dis[N] , ans , num;void aa(int x , int y , int z){	tt[++cc] = y , ll[cc] = z , nn[cc] = hh[x] , hh[x] = cc;}void add(int x , int y , int z){	to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;}bool cmp(int a , int b){	return tt[a] < tt[b];}void dijkstra(){	int x , i;	memset(dd , 0x3f , sizeof(dd));	dd[1] = 0 , q.push(make_pair(0 , 1));	while(!q.empty())	{		x = q.top().second , q.pop();		if(vv[x]) continue;		vv[x] = 1;		for(i = hh[x] ; i ; i = nn[i])			if(dd[x] == dd[tt[i]] + ll[i])				v[tt[i]].push_back(i ^ 1);		for(i = hh[x] ; i ; i = nn[i])			if(dd[tt[i]] > dd[x] + ll[i])				dd[tt[i]] = dd[x] + ll[i] , q.push(make_pair(-dd[tt[i]] , tt[i]));	}}void dfs(int x){	int i;	sort(v[x].begin() , v[x].end() , cmp);	for(i = 0 ; i < (int)v[x].size() ; i ++ )		if(!uu[tt[v[x][i]]])			uu[tt[v[x][i]]] = 1 , add(x , tt[v[x][i]] , ll[v[x][i]]) , add(tt[v[x][i]] , x , ll[v[x][i]]) , dfs(tt[v[x][i]]);}void getroot(int x , int fa){	int i;	bs[x] = 0 , si[x] = 1;	for(i = head[x] ; i ; i = next[i])		if(!vis[to[i]] && to[i] != fa)			getroot(to[i] , x) , si[x] += si[to[i]] , bs[x] = max(bs[x] , si[to[i]]);	bs[x] = max(bs[x] , sum - si[x]);	if(bs[x] < bs[root]) root = x;}void getdeep(int x , int fa){	int i;	for(i = head[x] ; i ; i = next[i])	{		if(!vis[to[i]] && to[i] != fa)		{			deep[to[i]] = deep[x] + 1 , dis[to[i]] = dis[x] + len[i] , md = max(md , deep[to[i]]);			if(dis[to[i]] > f[deep[to[i]]]) f[deep[to[i]]] = dis[to[i]] , sf[deep[to[i]]] = 1;			else if(dis[to[i]] == f[deep[to[i]]]) sf[deep[to[i]]] ++ ;			getdeep(to[i] , x);		}	}}void query(int x){	int i , j , sm = 0;	vis[x] = 1;	for(i = head[x] ; i ; i = next[i])	{		if(!vis[to[i]])		{			md = deep[to[i]] = 1 , dis[to[i]] = len[i] , f[1] = len[i] , sf[1] = 1 , getdeep(to[i] , x);			for(j = 1 ; j <= md && j <= k ; j ++ )			{				if(ans < f[j] + g[k - j]) ans = f[j] + g[k - j] , num = sf[j] * sg[k - j];				else if(ans == f[j] + g[k - j])num += sf[j] * sg[k - j];			}			for(j = 1 ; j <= md && j <= k ; j ++ )			{				if(g[j] < f[j]) g[j] = f[j] , sg[j] = sf[j];				else if(g[j] == f[j]) sg[j] += sf[j];			}			for(j = 1 ; j <= md ; j ++ ) f[j] = -inf , sf[j] = 0;			sm = max(sm , md);		}	}	for(i = 1 ; i <= sm && i <= k ; i ++ ) g[i] = -inf , sg[i] = 0;	for(i = head[x] ; i ; i = next[i])		if(!vis[to[i]])			root = 0 , sum = si[to[i]] , getroot(to[i] , x) , query(root);}int main(){	int m , i , x , y , z;	scanf("%d%d%d" , &n , &m , &k) , k -- ;	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%d" , &x , &y , &z) , aa(x , y , z) , aa(y , x , z);	dijkstra() , uu[1] = 1 , dfs(1);	memset(f , 0xc0 , sizeof(f)) , memset(g , 0xc0 , sizeof(g)) , g[0] = 0 , sg[0] = 1;	bs[0] = inf , sum = n , getroot(1 , 0) , query(root);	printf("%d %d\n" , ans , num);	return 0;}

 

 

【bzoj4016】[FJOI2014]最短路径树问题 堆优化Dijkstra+DFS树+树的点分治