[原创]计蒜之道 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≠zd(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(4≤n≤300)n(4 \leq n \leq 300)，表示该地区的点数。

接下来输入 n 行，每行输入 n 个整数。第 i行第 j 个数Gi,j(−1≤Gi,j≤10000;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(n3log⁡n)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;
}