首页 > 代码库 > 【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树+树的点分治
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。