2016计蒜之道复赛 百度地图的实时路况(Floyd 分治)
程序员文章站
2022-07-05 15:40:25
题意 "题目链接" Sol 首先一个结论:floyd算法的正确性与最外层$k$的顺序无关(只要保证是排列即可) 我大概想到一种证明方式就是把最短路树上的链拿出来,不论怎样枚举都会合并其中的两段,所以正确性是对的 这道题的话显然一个$n^4$的暴力是枚举哪个点不选,再跑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; }
上一篇: 洛谷P2000 拯救世界(生成函数)
下一篇: 设计模式面试