题解：P11819 [PA 2019 Final] Floyd-Warshall

尝试刻画这个错误的 floyd 能得到哪些路径，发现其实没有那么复杂，还是刻画得出来的。

下面约定

i\sim j

表示

i

到

j

的一条有向路径，

i\to j

表示

i

到

j

的一条有向边。

假设现在最外层枚举到

(s,t)

（这里假设

s<t

，不满足可以建反图再跑一遍），那么下面这些

s\sim t

的路径会被考虑：

$s\to t$ ；
$s\to p\to t$ ；
$s\sim p\to t$ ，其中 $s<p<t$ ，且 $s\sim p$ 的路径会被考虑；
$s\sim p\sim t$ ，其中 $p<s$ ，且 $s\sim p$ 和 $p\sim t$ 的路径会被考虑。

注意这是一个递归的结论。可以归纳出，所有

s\sim t

（假设

s<t

）的被考虑的路径为以下形式：

s\to p_1\to p_2\to\dots\to p_k\to\dots\to p_l

其中，

k

可以等于

l

，且有以下性质：

$p_l=t$ ， $p_k>s$ ；
$\forall i\in[k,l),p_i<p_{i+1}$ ；
$\nexists i\in[2,k),\min(p_i,p_{i-1})>s$ 。

也就是说，所有被考虑的从

s

到

t

的路径都是从

s

开始在原图上走，但是不能连续两步都在

\geq s

的点上；然后在第一次违反这个限制后只能向编号更大的点走，最终走到

t

。

这是一个非常好的结论，以至于我们可以直接利用它来求出错误的最短路。

首先枚举

s

，忽略两端都大于

s

的边后跑一遍最短路，可以考虑到

s\sim p_{k-1}

的所有路径；然后保留原图上的所有边，可以考虑到

p_{k-1}\to p_k

；最后只保留从编号小的点到编号大的点的边，可以考虑到

p_k\sim p_l

。将这三部分拼起来就可以求出错误的最短路了。

时间复杂度为

O(n(n+m)\log n)

，空间复杂度为

O(n^2+m)

，可以求出题面代码给出的最短路矩阵。在本题中空间也可以做到

O(n+m)

，可以把空间限制开到 1M。

下面是代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2222;
int n,m,D[N],t[N],o[N],p;
vector<pair<int,int> >e[N],g[N];
void dij(vector<pair<int,int> >*E,int S,int L,int*s){
	for(int i=1;i<=n;i++) o[i]=s[i]=1e9;
	priority_queue<pair<int,int> >q;
	for(q.push({s[S]=0,S});q.size();){
		int x=q.top().second;
		q.pop();
		if(o[x]<1e9) continue;
		o[x]=s[x];
		for(auto[i,v]:E[x]) if(i<=L||x<=L) if(s[i]>v+s[x]) q.push({-(s[i]=v+s[x]),i});
	}
	for(int i=1;i<=n;i++) for(auto[j,v]:E[i]) s[j]=min(s[j],o[i]+v);
	for(int i=L+1;i<=n;i++) for(auto[j,v]:E[i]) if(j>i) s[j]=min(s[j],s[i]+v);
}
int main(){
	cin>>n>>m;
	for(int i=1,j,k,l;i<=m;i++){
		scanf("%d %d %d",&j,&k,&l);
		e[j].push_back({k,l});
		g[k].push_back({j,l});
	}
	for(int i=1;i<=n;i++){
		dij(e,i,n,D);
		dij(e,i,i,t);
		for(int j=i+1;j<=n;j++) p+=t[j]!=D[j];
	}
	for(int i=1;i<=n;i++){
		dij(g,i,n,D);
		dij(g,i,i,t);
		for(int j=i+1;j<=n;j++) p+=t[j]!=D[j];
	}
	cout<<p;
}

题解：P11819 [PA 2019 Final] Floyd-Warshall

文章操作

相关推荐

评论

题解：P11819 [PA 2019 Final] Floyd-Warshall