题目
分析
首先把最短路径树画出来(由题意最短路径唯一,所以是树):
其中1是根。我们将树记作T,i的子树记作B。图中,B是绿色点,T-B是红色点。
而1~i最短路上的最后一条边(也就是不能走的边)即i的父亲边。将这条边去掉以后,1~i的最短路长什么样呢?
可以发现,一定是这样的:
即,先从1沿着树边走到T-B中的某个点u,然后再沿着某条非树边走到B中的某个点v,然后再沿着树边走到i。
为什么这样是对的呢?假设这条最短路上最后一个T-B中的点是u,那么1~u一定是走最短路(即树边),然后u~v的那条边一定是非树边(T中去掉i的父亲边后,B和T-B不再相连),然后v~i的最短路一定也是树边(否则我们可以求出一个1~v的更短路,矛盾)。
假设1~i的最短路是f[i](即树中1~i的长度)。那么,每一条如上所述的路径由某条边(u,v)唯一确定。这条边满足:
①不是i的父亲边。
②u不在B中,而v在B中。
(题中是无向边,我们拆成两条有向边即可)
而路径的长度就是f[u]+f[v]+w(u,v)-f[i]。w(u,v)是边(u,v)的长度。
换言之,设f[u]+f[v]+w(u,v)=g(u,v)。那么对于i,我们需要找到g(u,v)最小的(u,v),使得u在T-B中而且v在B中(且(u,v)不是i的父亲边),那么i的答案就是g(u,v)-f[i]。
怎么找呢?DFS下去,在每个点处维护一个可合并(小根)堆,里面存放所有u在i子树内的(u,v)。一个儿子的DFS结束后,就将它的堆和当前i的堆合并,然后再往i的堆里插入所有i引出的边。然后,如果堆顶不符合条件(即v也在i的子树内),就不断地将堆顶元素弹出,直到堆顶是一个合法的(u,v),这时它一定是i的答案。
有一个细节:这里需要快速判断“v是否在i的子树内”,怎么办呢?用并查集,在儿子DFS结束后,将其并查集和i的合并,这样通过查找v和i是否位于同一并查集,就可以快速判断了。
时间复杂度O(NlogN)。注意,一开始求最短路用SPFA会TLE,必须用Dijkstra,可能是数据故意卡。
代码
#include#include #include #include #include #include using namespace std; const int SIZEN=100010,SIZEM=400010; const int INF=0x7fffffff/2; class Edge{ public: int u,v; int len; int sum;//两端的depth之和加上len }; class Node{//小根堆左偏树的节点 public: int l,r; int h; Edge e; #define l(x) tree[x].l #define r(x) tree[x].r #define h(x) tree[x].h #define e(x) tree[x].e }; Node tree[SIZEM]; int node_merge(int u,int v){ if(!u||!v) return u+v; if(e(u).sum>e(v).sum) swap(u,v); r(u)=node_merge(r(u),v); if(h(l(u)) c[SIZEN]; int depth[SIZEN]={0}; int father[SIZEN]={0}; int ans[SIZEN]={0}; int root[SIZEN]={0}; int vis[SIZEN]={0}; void DFS(int x){ if(vis[x]) return; vis[x]=true; for(int i=0;i > Q; bool used[SIZEN]; void Dijkstra(int s){ for(int i=1;i<=N;i++) depth[i]=INF; depth[s]=0;Q.push(make_pair(-depth[s],s)); while(!Q.empty()){ int x=Q.top().second;Q.pop(); if(used[x]) continue; used[x]=true; for(int i=0;i