P1084 疫情控制

Solution

二分答案, 尽量往上跳, 不能跳到根节点.

仍然能跳的拿出来.看剩下的点没有覆盖哪个?

贪心的分配一下.
Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int N = 50005;

int n, m;

struct Edge {

    int v, c; Edge* nxt;

    Edge(int _, int __, Edge* ___) :

            v(_), c(__), nxt(___) {}

} *head[N];

void AddEdge(int u, int v, int c) {

    head[u] = new Edge(v, c, head[u]);

    head[v] = new Edge(u, c, head[v]);

}

int f[N][18], p[N]; long long dis[N][18];

void dfs(int u, int fa, long long distan) {

    f[u][0] = fa, dis[u][0] = distan;

    for (int i = 1; i <= 17; i += 1) {

        f[u][i] = f[f[u][i - 1]][i - 1];

        dis[u][i] = dis[u][i - 1] + dis[f[u][i - 1]][i - 1];

    }

    for (auto edge = head[u]; edge; edge = edge->nxt) {

        if (edge->v != fa)

            dfs(edge->v, u, edge->c);

    }

}

struct node {

    node() {}

    long long rest; int id;

    node(int _id, int _r) :

        id(_id), rest(_r) {}

    bool operator < (const node& o) const {

        return rest < o.rest;

    }

} a[N], b[N];

int vis[N], used[N], R[N];

long long Min[N];

int A, B;

int Dfs(int u, int fa) {

    int f1 = true, noleaf = false;

    if (vis[u]) return true;

    for (auto edge = head[u]; edge; edge = edge->nxt) {

        if (edge->v == fa) continue;

        noleaf = true;

        if (not Dfs(edge->v, u)) {

            f1 = 0;

            if (u == 1)

                b[B++] = node(edge->v, edge->c);

            else return false;

        }

    }

    if (not noleaf) return false;

    return f1;

}

int check(long long lim) {

    int u, now;

    long long num;

    A = B = 0;

    for (int i = 1; i <= n; i += 1) vis[i] = 0;

    for (int i = 1; i <= n; i += 1) R[i] = 0;

    for (int i = 1; i <= m; i += 1) used[i] = 0;

    for (int i = 1; i <= m; i += 1) {

        u = p[i], num = 0;

        for (int j = 17; ~j; j -= 1)

            if (f[u][j] > 1 and num + dis[u][j] <= lim)

                num += dis[u][j], u = f[u][j];

        if (f[u][0] == 1 and num + dis[u][0] <= lim) {

            a[A++] = node(i, lim - num - dis[u][0]);

            if (not R[u] or a[A].rest < Min[u])

                Min[u] = a[A].rest, R[u] = i;

        } else vis[u] = 1;

    }

    if (Dfs(1, 0)) return true;

    sort(a, a + A);

    sort(b, b + B);

    now = 0, used[0] = 1;

    for (int i = 0; i < B; i += 1) {

        if (!used[R[b[i].id]]) {

            used[R[b[i].id]] = 1; continue;

        }

        while (now < A and (used[a[now].id] or a[now].rest < b[i].rest)) now += 1;

        if (now >= A) return false;

        used[a[now].id] = true;

    }

    return 1;

}

int main() {

    scanf("%d", &n);

    for (int i = 1, u, v, c; i < n; i += 1) {

        scanf("%d%d%d", &u, &v, &c);

        AddEdge(u, v, c);

    }

    dfs(1, 0, 0);

    scanf("%d", &m);

    int l = 0, r = 5e5, mid;

    for (int i = 1; i <= m; i += 1) scanf("%d", &p[i]);

    while (l <= r) {

        mid = l + r >> 1;

        if (check(mid)) r = mid - 1;

        else l = mid + 1;

    }

    printf("%d\n", l);

    return 0;

}
巴特西

P1084 疫情控制

Solution

Code

最新文章

热门文章
