[原创]计蒜之道 2016复赛A 百度地图的实时路况 [floyd+分治]【图论】
[原创]计蒜之道 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 =\sum_{1 \leq x,y,z \leq n , x \neq y , y \neq z}{d(x,y,z)}$$ 现在我们知道了该地区的 nn 个点，以及若干条有向边，求该地区的交通便捷程度 PP。 输入格式 第一行输入一个正整数 $n(4 \leq n \leq 300)$，表示该地区的点数。 接下来输入 n 行，每行输入 n 个整数。第 i行第 j 个数 $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(n^4)$显然会TLE 然后想有没有其他优秀的图论东西能够快速的解决，发现没有， 最后我们采取的是分治的思路； 每次分为两段递归分治下去，将另一半所在的点给其他点进行松弛，也就是floyd的过程 然后这题的总复杂度度就能在$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;
}
|
