点分治的重心选择会影响正确性吗?
查看原帖
点分治的重心选择会影响正确性吗?
393767
bmatrix楼主2024/1/10 22:10

我感觉不会,所以求各位大佬分析一下我的代码:

#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
template<class T = int> const T& read() {
    static T x; cin >> x; return x;
}
constexpr int N = 2e5 + 5, K = 1e6 + 5, inf = 0x3f3f3f3f;
int n, k, ans = inf;
vector<pii> to[N];
int sz[N], mx[N], rt;
bitset<N> vis;
int buc[K];
vector<int> modi;
void getrt(int u, int f, int tot) {
    sz[u] = 1;
    mx[u] = 0;
    for(auto i : to[u]) {
        int v = i.F, w = i.S;
        if(!vis[v] && v != f) {
            getrt(v, u, tot);
            sz[u] += sz[v];
            gmax(mx[u], sz[v]);
        }
    }
    gmax(mx[u], tot - sz[u] - 1);
    if(mx[u] < mx[rt]) rt = u;
}
void dfs1(int u, int f, int s, int dep) {
    if(s > k) return;
    gmin(ans, dep + buc[k - s]);
    for(auto i : to[u]) {
        int v = i.F, w = i.S;
        if(!vis[v] && v != f) 
            dfs1(v, u, s + w, dep + 1);
    }
}
void dfs2(int u, int f, int s, int dep) {
    if(s > k) return;
    if(buc[s] > dep) buc[s] = dep, modi.emplace_back(s);
    for(auto i : to[u]) {
        int v = i.F, w = i.S;
        if(!vis[v] && v != f)
            dfs2(v, u, s + w, dep + 1);
    }
}
void slove(int u, int f, int tot) {
    rt = 0;
    getrt(u, f, tot);
    int r = rt;
    vis[r] = 1;
    for(auto i : to[r]) 
        if(!vis[i.F]) slove(i.F, r, sz[i.F]);
    buc[0] = 0;
    for(auto i : to[r]) {
        int v = i.F, w = i.S;
        if(!vis[v]) {
            dfs1(v, u, w, 1);
            dfs2(v, u, w, 1);
        }
    }
    buc[0] = inf;
    while(!modi.empty()) {
        buc[modi.back()] = inf;
        modi.pop_back();
    }
    vis[r] = 0;
}
signed main() {
#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#endif
    cin >> n >> k;
    rep(i, 1, n - 1) {
        int u, v, w; 
        cin >> u >> v >> w;
        ++u, ++v;
        to[u].emplace_back(v, w);
        to[v].emplace_back(u, w);
    }
    memset(mx, 0x3f, sizeof mx);
    memset(buc, 0x3f, sizeof buc);
    slove(1, 0, n);
    cout << (ans == inf ? -1 : ans) << endl;
    return 0;
}

这份代码在洛谷会 WA 85,当我将第 62 行(slove 函数内)改成这样之后:

if(!vis[i.F]) slove(i.F, r, sz[i.F] + 1);

就 AC 了,我不理解,各位大佬能解答一下吗/kk

2024/1/10 22:10
加载中...