[原创]计蒜之道 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=1x,y,zn,xy,yzd(x,y,z)P =\sum_{1 \leq x,y,z \leq n , x \neq y , y \neq z}{d(x,y,z)}

现在我们知道了该地区的 nn 个点,以及若干条有向边,求该地区的交通便捷程度 PP。

输入格式

第一行输入一个正整数n(4n300)n(4 \leq n \leq 300),表示该地区的点数。

接下来输入 n 行,每行输入 n 个整数。第 i行第 j 个数Gi,j(1Gi,j10000;Gi,i=0)G_{i,j}(-1 \leq G_{i,j} \leq 10000;G_{i,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)O(n^4)显然会TLE

然后想有没有其他优秀的图论东西能够快速的解决,发现没有,

最后我们采取的是分治的思路;

每次分为两段递归分治下去,将另一半所在的点给其他点进行松弛,也就是floyd的过程

然后这题的总复杂度度就能在O(n3logn)O(n^3\log n)的时间复杂下解决了

附本题代码
——————————————————————————————————————————

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;
}