专栏首页数据结构与算法2016计蒜之道复赛 百度地图的实时路况(Floyd 分治)

2016计蒜之道复赛 百度地图的实时路况(Floyd 分治)

题意

题目链接

Sol

首先一个结论:floyd算法的正确性与最外层\(k\)的顺序无关(只要保证是排列即可)

我大概想到一种证明方式就是把最短路树上的链拿出来,不论怎样枚举都会合并其中的两段,所以正确性是对的

这道题的话显然一个\(n^4\)的暴力是枚举哪个点不选,再跑floyd。

这个暴力等价于求出每个点除它之外的Floyd矩阵

那么考虑暴力分治,每次找一个中间点\(mid\),暴力向左右递归即可

时间复杂度:\(O(n^3 logn)\)

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 301;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, g[MAXN][MAXN];
LL ans = 0;
void chmin(int &a, int b) {a = (a < b ? a : b);}
void solve(int l, int r) {
    if(l == r) {
        for(int i = 1; i <= N; i++) 
            for(int j = 1; j <= N; j++) 
                if(i != l && j != l) ans += (g[i][j] == 1e9 ? -1 : g[i][j]);
        return ;
    }
    int f[MAXN][MAXN];
    memcpy(f, g, sizeof(g));
    int mid = l + r >> 1;
    for(int k = mid + 1; k <= r; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                if(i != k && j != k) chmin(g[i][j], g[i][k] + g[k][j]);
    solve(l, mid);
    memcpy(g, f, sizeof(g));    
    for(int k = l; k <= mid; k++) 
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                if(i != k && j != k) chmin(g[i][j], g[i][k] + g[k][j]); 
    solve(mid + 1, r);
    memcpy(g, f, sizeof(g));
}
int main() {
    N = read();
    for(int i = 1; i <= N; i++)     
        for(int j = 1; j <= N; j++) {
            g[i][j] = read();
            if(g[i][j] == -1) g[i][j] = 1e9;
        }
    solve(1, N);
    cout << ans;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P2264 情书(字符串hash90分)

    题目背景 一封好的情书需要撰写人全身心的投入。lin_toto同学看上了可爱的卡速米想对她表白,但却不知道自己写的情书是否能感动她,现在他带着情书请你来帮助他。...

    attack
  • 1576 最长严格上升子序列

    1576 最长严格上升子序列  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给...

    attack
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • BZOJ4337: BJOI2015 树的同构(hash 树同构)

    attack
  • Lake Counting (POJ No.2386)

    题意:有一个M*N的圈子,雨后有积水,然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

    用户7727433
  • 洛谷P2196 挖地雷(dp)

    attack
  • cf547D. Mike and Fish(欧拉回路)

    attack
  • 1576 最长严格上升子序列

    1576 最长严格上升子序列  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给...

    attack
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • P2264 情书(字符串hash90分)

    题目背景 一封好的情书需要撰写人全身心的投入。lin_toto同学看上了可爱的卡速米想对她表白,但却不知道自己写的情书是否能感动她,现在他带着情书请你来帮助他。...

    attack

扫码关注云+社区

领取腾讯云代金券