个人排位赛8补题记录

百度地图的实时路况 (计蒜客 A1108)

题意：$d(x,y,z)$为$x$到$y$且不经过$z$的最短路长度，对于任意$(x,y,z)(x\ne z,y\ne z,1\le x,y,z\le n)$，求$\sum d(x,y,z)$

分治Flody

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, int>  
#define sqr(x) ((x)*(x))
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 302; // 开大了会出问题(比如350)

ll ans = 0;
int G[maxn][maxn], n;

void flody(int l, int r){
    if(l == r){
        for(int i=1; i<=n; i++){
            if(i == l) continue;
            for(int j=1; j<=n; j++){
                if(j == l) continue;
                ans += G[i][j]==inf?-1:G[i][j];
            }
        }
        return;
    }
    int cache[maxn][maxn];
    memcpy(cache, 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++){
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
    flody(l, mid);

    memcpy(G, cache, sizeof(G));
    for(int k=l; k<=mid; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
    flody(mid + 1, r);
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) {
            cin >> G[i][j];
            if(G[i][j] == -1) G[i][j] = inf;
        }
    }
    flody(1, n);
    cout << ans << '\n';
}

signed main(){
    Android;
    solve();
}

商汤智能机器人 (计蒜客 A1245) Lucas

题解:https://www.jisuanke.com/article/4y3zvj7z

占坑

Electricity Connection (UVA 12254) 斯坦纳树问题

参考题解: https://morris821028.github.io/2018/08/19/uva-12254/

斯坦纳树笔记