洛谷P2491 [SDOI2011]消防

zrzring 2020-10-08 PM 35℃ 0条

不管数据怎么样,还是要做到最完美的解法

枢纽会切开若干极长路径并对一条极长路径造成影响,使得其被切开后的极长路径变小

形象表述是会把一条极长路径切两刀留两边的两段,其他路径会被切一刀留两段或不被切

根据这一特点,很容易想到可能是直径

考虑直径的性质,无论从直径上哪个点出发,都不会从非该直径的区域,找到更长的路径,否则这就不是一条直径

于是枢纽肯定建立在某条直径上减小直径对答案的影响

具体做法,找到直径后在直径上跑一个双指针使得直径的贡献最小,然后和直径外的贡献取max就是答案

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

void file() {
    freopen("std.in", "r", stdin);
    freopen("wa.out", "w", stdout);
}

const int N = 1e6 + 10, M = 2e6 + 10, inf = 0x3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct EDGE {
    int u, v, nxt, dis;
} edge[N];

int n, m, head[N], cnt, dis[N], to[N], L, R, S, T, vis[N], ans, a[N], q[N];

int pre[N], suf[N], pnt[N];

void add(int u, int v, int t) {edge[++cnt] = (EDGE){u, v, head[u], t}; head[u] = cnt;}

void dfs1(int u, int last) {
    to[u] = u; dis[u] = 0;
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].v; if (v == last) continue;
        dfs1(v, u); if (dis[v] + edge[e].dis > dis[u]) {
            dis[u] = dis[v] + edge[e].dis; to[u] = to[v];
        } 
    }
}

void dfs2(int u, int last) {
    dis[u] = 0;
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].v; if (v == last) continue; dfs2(v, u);
        if (vis[v]) continue; dis[u] = max(dis[u], dis[v] + edge[e].dis);
    }
    ans = max(dis[u], ans);
}

int main() {
    n = read(); m = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(), t = read(); add(u, v, t); add(v, u, t);
    }
    dfs1(1, 0); S = to[1]; dfs1(S, 0); T = to[S];
    for (int i = 1; i <= n; i++) if (to[i] == T) vis[i] = 1;
    int u = S, l = 1, r = 1, res = inf; cnt = 0;
    while (u != T) {
        vis[u] = 0; pnt[++cnt] = u;
        for (int e = head[u]; e; e = edge[e].nxt) {
            int v = edge[e].v; if (vis[v]) {a[cnt] = edge[e].dis; u = v; break;}
        }
    }
    pnt[++cnt] = T;
    for (int i = 1; i <= cnt - 1; i++) pre[i] = pre[i - 1] + a[i];
    for (int i = cnt - 1; i >= 1; i--) suf[i] = suf[i + 1] + a[i];
    for (int i = cnt; i >= 1; i--) pre[i] = pre[i - 1];
    for (r = 1; r <= cnt; r++) {
        while (pre[r] - pre[l] > m) l++;
        if (max(pre[l], suf[r]) < res) L = l, R = r, res = max(pre[l], suf[r]);
    }
    for (int i = L; i <= R; i++) vis[pnt[i]] = 1; dfs2(S, 0);
    printf("%d", max(ans, res));
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00