模拟赛 路径和

题目描述

对于一张有向图，定义 $d(u,v,w)$ 为从 $u$ 号点出发，不经过 $v$ 号点，最终到达w号点的最短路径长度。如果不存在这样的路径，$d(u,v,w)$ 的值为$-1$。 你也可以认为 $d(u,v,w)$ 是删去 $v$ 点和其相关的边后，图中 $u$ 到 $w$ 的最短路。 现在给定这张有向图每两个点之间的有向边的长度（如果不存在连边则为$-1$），对于所有满足 $1⩽x,y,z⩽n,x\ne y,y\ne z$的有序数对 $(x,y,z)$，求它们 $d(x,y,z)$ 的和。 $1⩽n⩽300$ 时间限制2s，空间限制512MB。

题解

此题显然可以枚举每个点 $i$，删除后利用Floyd算法算出所有的 $d(x,i,z)$。时间复杂度 $O(n^4)$。 根据Floyd的原理，首先枚举最短路径中转点，而枚举中转点的顺序对答案并不影响，所以可以把删点改为枚举中转点时跳过改点。 设现在要求的除去 $x$ 号点后的Floyd最终矩阵。若现已知除去区间 $[l,r]$ 的点后的矩阵，令 $mid=\lfloor \frac{l+r}{2}\rfloor$，区间 $[l,mid]$ 的答案可以在区间 $[l,r]$ 的基础上枚举区间 $[mid+1,r]$ 中的点为中转点，更新矩阵。区间 $[mid+1,r]$ 同理。最终按原方式统计答案。时间复杂度 $O(n^{3}lo{g}_{2}n)$，空间复杂度 $O(n^3)$。 做此类问题要利用经典算法的原理，思路要开阔。

代码：

#include<stdio.h> #define R register int #define L long long #define I inline void int dis[1200][301][301]; I Calc(int p,int x,int&n,L&ans){ for(R i=1;i<=n;i++){ if(i!=x){ for(R j=1;j<=n;j++){ if(j!=x){ ans+=dis[p][i][j]==5e6?-1:dis[p][i][j]; } } } } } I Solve(int p,int l,int r,int&n,L&ans){ if(l==r){ Calc(p,r,n,ans); }else{ int mid=l+r>>1,Ls=p<<1,Rs; Rs=Ls|1; for(R i=1;i<=n;i++){ for(R j=1;j<=n;j++){ dis[Ls][i][j]=dis[Rs][i][j]=dis[p][i][j]; } } for(R i=mid+1;i<=r;i++){ for(R j=1;j<=n;j++){ for(R k=1;k<=n;k++){ if(dis[Ls][j][k]>dis[Ls][j][i]+dis[Ls][i][k]){ dis[Ls][j][k]=dis[Ls][j][i]+dis[Ls][i][k]; } } } } for(R i=l;i<=mid;i++){ for(R j=1;j<=n;j++){ for(R k=1;k<=n;k++){ if(dis[Rs][j][k]>dis[Rs][j][i]+dis[Rs][i][k]){ dis[Rs][j][k]=dis[Rs][j][i]+dis[Rs][i][k]; } } } } Solve(Ls,l,mid,n,ans); Solve(Rs,mid+1,r,n,ans); } } int main(){ int n; scanf("%d",&n); for(R i=1;i<=n;i++){ for(R j=1;j<=n;j++){ scanf("%d",dis[1][i]+j); if(dis[1][i][j]==-1){ dis[1][i][j]=5e6; } } } L ans=0; Solve(1,1,n,n,ans); printf("%lld",ans); return 0; }