[USACO Jan09]安全路径Safe Travel解题报告

题目


分析

首先把最短路径树画出来(由题意最短路径唯一,所以是树):



其中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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注