[原创]计蒜之道 2016复赛A 百度地图的实时路况 [floyd+分治]【图论】
2017-06-09 09:58:13 Tabris_ 阅读数:514
博客爬取于2020-06-14 22:40:02
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72953925
题目链接:https://nanti.jisuanke.com/t/11217
——————————————————————————————————————————
百度地图的实时路况功能相当强大,能方便出行的人们避开拥堵路段。一个地区的交通便捷程度就决定了该地区的拥堵情况。假设一个地区有 nn 个观测点,编号从 11 到 nn。定义 d(u,v,w)d(u,v,w) 为从 uu 号点出发,严格不经过 vv 号点,最终到达 ww 号点的最短路径长度,如果不存在这样的路径,d(u,v,w)d(u,v,w) 的值为 -1−1。
那么这个地区的交通便捷程度 PP 为:
P=1≤x,y,z≤n,x=y,y=z∑d(x,y,z)
现在我们知道了该地区的 nn 个点,以及若干条有向边,求该地区的交通便捷程度 PP。
输入格式
第一行输入一个正整数n(4≤n≤300),表示该地区的点数。
接下来输入 n 行,每行输入 n 个整数。第 i行第 j 个数Gi,j(−1≤Gi,j≤10000;Gi,i=0)表示从 i 号点到 j 号的有向路径长度。如果这个数为 −1,则表示不存在从 ii 号点出发到 jj 号点的路径。
输出格式
输出一个整数,表示这个地区的交通便捷程度。
样例输入
4
0 1 -1 -1
-1 0 1 -1
-1 -1 0 1
1 -1 -1 0
样例输出
4
——————————————————————————————————————————
正常做法是枚举每个点之后对其他点进行floyd,这样的话复杂度是O(n4)显然会TLE
然后想有没有其他优秀的图论东西能够快速的解决,发现没有,
最后我们采取的是分治的思路;
每次分为两段递归分治下去,将另一半所在的点给其他点进行松弛,也就是floyd的过程
然后这题的总复杂度度就能在O(n3logn)的时间复杂下解决了
附本题代码
——————————————————————————————————————————
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| # include<bits/stdc++.h> typedef long long int LL; using namespace std;
const int N = 333+7; const int MOD = 1e9+7; const int INF = (~(1<<31))>>1;
# define abs(x) ((x)>0?(x):-(x))
/****************************************************/
int n; int m[N][N]; int dp[20][N][N]; LL ans; void solve(int d,int l,int r){ if(l==r){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)if(j!=l&&i!=l) if(dp[d][i][j]==INF) ans+=-1; else ans+=dp[d][i][j]; return ; } int m = r+l >> 1;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[d+1][i][j]=dp[d][i][j];
for(int k=m+1;k<=r;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dp[d+1][i][j]>dp[d+1][i][k]+dp[d+1][k][j]) dp[d+1][i][j]=dp[d+1][i][k]+dp[d+1][k][j];
solve(d+1,l,m);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[d+1][i][j]=dp[d][i][j];
for(int k=l;k<=m;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(dp[d+1][i][j]>dp[d+1][i][k]+dp[d+1][k][j]) dp[d+1][i][j]=dp[d+1][i][k]+dp[d+1][k][j];
solve(d+1,m+1,r); }
int main(){ scanf("%d",&n);ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&dp[1][i][j]); if(dp[1][i][j]==-1) dp[1][i][j]=INF; } }
solve(1,1,n);
printf("%lld\n",ans);
return 0; }
|