题解：P14184 有向无权图删边最短路

upd on 2025/10/17：修改了错误内容，现在时间复杂度是正确的，可以不管评论区提到的错误了。

如有不对请再次提出，我会虚心改正的。

本文摘抄自 EI's blog，稍微进行了一些补充。

我们先求出一条

s

到

t

的某条最短路。然后不在这条最短路上的边删去不影响最短路，直接得出结果。

于是我们只需要考察这条路径上每条边被删除的时候的最短路。

对比原来的最短路，容易发现删边后 只需要离开原来的最短路一次。

具体的：记原来的最短路为

p_1=1,p_2,\dots,p_k=n

，那么新的最短路在

p_i

处离开，在

p_j

处重新回来，且

i<j

。

考虑设置阈值

B

，当

p_i

到

p_j

的这条外部路径的长度超过或不超过

B

的时候，我们分别处理。

短

注意到从

p_i

到

p_j

的一条外部路径长度一定不小于

j-i

。

我们可以一次性处理所有

i \bmod (B+1)

为同一个值作为起点的

i

。因为

i-B-1<i\le j

时候，

i-B-1

的贡献一定

>B

，在此时就没有影响。

从它们开始做多源 BFS，可以在

\mathcal{O}(m)

的时间内得到到每个点的对应的外部路径长度。

具体怎么做呢？

称路径上

\bmod\ B+1=r

的点为当前的关键点。

多源 BFS 时候起点要有初始权值

dis_u

，就是原来的最短路。

然后考虑按顺序加入关键点，假设加入到

u

。并且 BFS 的时候强制要求路径长度不能超过

dis_u+B

，这样就不会有多余的影响。

最后再做一个类似后缀

\min

的东西，具体请参考代码理解。

这部分复杂度为

\mathcal{O}(mB)

。

长

随机选一个点，考虑用经过它的外部路径来更新答案。

只需要在正图和反图上做 BFS 以及做前缀、后缀的

\min

就能在

\mathcal{O}(m)

时间内更新。

由于我们考虑的都是

\ge B

的路径，所以每条路径有

\ge \frac{B}{n}

的概率命中。

随机

\frac{n}{B}

次，就只有

\left(1 - \frac{B}{n}\right)^{\frac{n}{B}} \le \frac{1}{e}

的概率失败。

因此，总共随机

k\ln n \cdot \frac{n}{B}

次，根据 union bound 就保证了有

\ge 1 - n^{1- k}

的概率成功计算出所有答案。

这部分复杂度为

\mathcal{O}\left(m\log n\cdot \frac{n}{B} \right)

。

清算

综上，取

B=\sqrt {n\log n}

，我们在

\mathcal{O}\left(m\sqrt{n\log n}\right)

的时间内解决。

根据两边常数，实际取 $B=4000$ 较好。 $k$ 在 $n$ 比较大时直接取 $2$ 就行。

代码

CPP

// 洛谷 P14184
// https://www.luogu.com.cn/problem/P14184
#include<bits/stdc++.h>
#define LL long long
#define bs basic_string<int>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
mt19937 rnd(time(0));
const int N=1e5+5,B=4000,inf=0x3f3f3f3f;
int n,m,d[N],u[N],pre[N],ans[N],t,a[N],b[N],p[N];bool in[N],v[N];
struct node{int u,v;}e[N];
vector<pair<int,int>>E[N];bs G[N],_G[N];
inline void cmn(int &x,int y){x=min(x,y);}
inline void gd()
{
	fill_n(d+1,n,-1);d[1]=0;
	queue<int>q;q.push(1);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(auto [y,w]:E[x]) if(d[y]==-1)
			d[y]=d[x]+1,pre[y]=w,q.push(y);
	}
	if(d[n]==-1){while(m--) puts("-1");exit(0);}
	for(int i=n;i!=1;)
	{
		in[pre[i]]=1;b[++t]=pre[i];
		auto [u,v]=e[pre[i]];i^=u^v;a[t]=i;
	}
	reverse(a+1,a+1+t);reverse(b+1,b+1+t);a[++t]=n;
	for(int i=1;i<=m;i++) if(!in[i])
	{
		auto [u,v]=e[i];
		ans[i]=d[n];G[u]+=v,_G[v]+=u;
	}memset(in,0,sizeof(in));
	for(int i=1;i<=t;i++) in[a[i]]=1;
}
int q[N],hd,tl;
inline void bfs(int x,auto G,int *d)
{
	fill_n(d+1,n,-1);hd=1,tl=0;
	d[x]=0,q[++tl]=x;
	while(hd<=tl)
	{
		int x=q[hd++];
		for(int y:G[x]) if(d[y]==-1)
			d[y]=d[x]+1,q[++tl]=y;
	}
}
inline void sm()
{
	int L=min(B,n);
	for(int o=0;o<=min(L,t);o++)
	{
		hd=1,tl=0;
		for(int i=1;i<=n;i++) v[i]=0,d[i]=inf;
		int nw=-1e9,T=1;
		while(hd<=tl||T<=t)
		{
			if(hd>tl||d[q[hd]]>nw)
			{
				while(T<=t&&(T-1)%(L+1)!=o) v[a[T++]]=1;
				if(T<=t)
				{
					d[a[T]]=T-1;int x=a[T++];
					nw=d[x]+L;q[++tl]=x;v[x]=1;
				}
			}
			if(hd>tl) continue;int x=q[hd++];
			if(d[x]>nw) continue;//nw 做限制
			for(int y:G[x]) if(!v[y]) d[y]=d[x]+1,v[y]=1,q[++tl]=y;
		}
		for(int i=t;i;i--) if((i-1)%(L+1)!=o)
		{
			int u=a[i],v=(i<t)?a[i+1]:0;
			if(i%(L+1)!=o&&v) d[u]=min(d[u],d[v]-1);
			cmn(ans[b[i-1]],d[u]+t-i);
		}//后缀 min 贡献
	}
}//多源 bfs
inline void bg()
{
	int T=2*log(n)*n/B;
	iota(p,p+1+n,0);shuffle(p+1,p+1+n,rnd);
	for(int i=1,x=p[1];i<=T;x=p[++i])
	{
		bfs(x,_G,d),bfs(x,G,u);fill_n(pre,t,inf);
		for(int i=1;i<t;i++){
			pre[i]=pre[i-1];
			if(~d[a[i]]) cmn(pre[i],d[a[i]]+i-1);
		}int mn=inf;
		for(int i=t;i>1;i--)
		{
			if(~u[a[i]]) cmn(mn,u[a[i]]+t-i);
			cmn(ans[b[i-1]],mn+pre[i-1]);
		}
	}
}//大的
int main()
{
	cin.tie(0)->sync_with_stdio(0);cout.tie(0);cin>>n>>m;
	for(int i=1,u,v;i<=m;i++) cin>>u>>v,e[i]={u,v},E[u].push_back({v,i});
	memset(ans,inf,sizeof(ans));gd();sm();bg();
	for(int i=1;i<=m;i++) cout<<(ans[i]>=n?-1:ans[i])<<"\n";
	return 0;
}

题解：P14184 有向无权图删边最短路

文章操作

短

长

清算

相关推荐

评论

题解：P14184 有向无权图删边最短路