P1084 疫情控制（二分+树上倍增+贪心）

题目描述

现在，在

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

题解：

首先问的是最长时间的最小值，显然应该用二分来求解。问题的关键是如何写这个check函数。

分析一下问题可以发现，在我们给定的时间内，每个军队肯定会选择优先向树根走来确保自己可以覆盖最大的统治，我们不妨先预处理出每个军队可以到达离根节点最近的位置（这部分用树上倍增实现）在每个

军队尽可能向上走完后，会出现一下情况。

1、当前军队已经耗尽了步数，只能停留在此地了

2、当前军队可以到达根节点，甚至到达了根节点之后还能继续行军，我们称之为预备军

接下来要判断的是以根节点的每个子节点为根的子树是否被完全隔断了，如果不是我们就让那些预备军去占领这些子树的根节点，怎么占领呢？接下来的贪心比较关键。

我们把预备军还能走的路程从小到大排序，同时把这些尚未被隔离的子树根节点到1号根节点的距离从小到大排序，那么最优的占领方法一定是从小打到的让那些预备军占领结点，具体的实现方式可以用类似双指针的方法实现。

如果可以实现，那么返回true，否则就返回false，最后可以二分出最终的答案。

具体见代码，思路不难理解，但是具体实现的代码其实还挺多细节需要注意的。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map> 
#include <stack>
#include <sstream>
#include <set>
#pragma GCC optimize(2)

//#define int long long
#define rush() int T;scanf("%d",&T);for(int Ti=1;Ti<=T;++Ti)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mm(i,v) memset(i,v,sizeof i);
#define mp(a, b) make_pair(a, b)
#define pi acos(-1)
#define fi first
#define se second
//你冷静一点，确认思路再敲！！！ 

using namespace std;
typedef long long ll;
typedef pair<int, int > PII;
priority_queue< PII, vector<PII>, greater<PII> > que;
stringstream ssin; //  ssin << string   while ( ssin >> int)

const int N = 5e4 + 5, M = 1e5 + 5, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m, idx, t, atot, btot, ctot;
int e[M], ne[M], w[M], h[N], query[N];
int depth[N], fa[N][20];
ll dist[N][20];
pair<ll, int> vec[N];
bool sta[N], need[N];
ll tim[N], ned[N];
ll sum;
queue<int>q;

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;
}

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void bfs() {
    q.push(1);
    for (int i = 0; i < N; ++i) {
        depth[i] = INF;
    }
    depth[1] = 1;
    depth[0] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i], z = w[i];
            if (depth[y] > depth[x] + 1) {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                dist[y][0] = z;
                for (int k = 1; k <= t; ++k) {
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
                    dist[y][k] = dist[fa[y][k - 1]][k - 1] + dist[y][k - 1];
                }
                q.push(y);
            }
        }
    }
}

bool dfs(int x) {
    bool pson = 1;
    if (sta[x]) return true;

    for (int i = h[x]; ~i; i = ne[i]) {
        int y = e[i];
        if (depth[y] < depth[x]) continue;
        pson = 0;
        if (!dfs(y)) return false;
    }
    if (pson) return false;
    
    return true;
}

void init() {
    for (int i = 0; i < N; ++i) {
        sta[i] = 0;
        ned[i] = 0;
        need[i] = 0;
        vec[i] = {0, 0};
        tim[i] = 0;
    }
    atot = 0;
    btot = 0;
    ctot = 0;
}

bool ck(ll lim) {
    init();
    for (int i = 1; i <= m; ++i) {
        ll x = query[i], cnt = 0;
        for (int j = t; j >= 0; --j) {
            if (fa[x][j] > 1 && cnt + dist[x][j] <= lim) {
                cnt += dist[x][j];
                x = fa[x][j];
            }
        }
        if (fa[x][0] == 1 && cnt + dist[x][0] <= lim) {   // 注意这些点是可以到达根节点的点，并且存储的距离也是到达根节点后还能移动的距离
            vec[++ctot] = mp(lim - cnt - dist[x][0], x);   // 仍然可以移动的点(相对于lim来说)
        } else sta[x] = 1;  // 已经确定位置的点
    }

    for (int i = h[1]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfs(v)) need[v] = 1;
    }
    sort(vec + 1, vec + 1 + ctot);
    for (int i = 1; i <= ctot; ++i) {
        if (need[vec[i].second] && vec[i].first < dist[vec[i].second][0]) {
            need[vec[i].second] = 0;
        } else {
            tim[++atot] = vec[i].first; // 剩下的所有可以移动的点所能移动的距离的集合
        }
    }

    for (int i = h[1]; ~i; i = ne[i]) {
        int v = e[i];
        if (need[v]) {
            ned[++btot] = dist[v][0];  // 以根结点的子节点为根的子树中存在有叶子结点未被完全隔离的 这些子节点到根节点的距离
        }
    }

    if (atot < btot) return false;

    sort(tim + 1, tim + 1 + atot);
    sort(ned + 1, ned + 1 + btot);

    int i = 1, j = 1;
    while (i <= btot && j <= atot) {
        if (tim[j] >= ned[i]) {
            i++;
            j++;
        } else {
            j++;
        }
    }
    if (i > btot) return true;
    return false;
}

int main()
{
    n = read();
    t = log2(n) + 1;
    mm(h, -1);
    for (int i = 1; i < n; ++i) {
        int a, b, c;
        a = read(); b = read(); c = read();
        sum += c;
        if (a > b) swap(a, b);
        add(a, b, c);
        add(b, a, c);
    }
    bfs();
    m = read();
    for (int i = 1; i <= m; ++i) query[i] = read();
    
    ll l = 0, r = sum;
    ll ans = -1;
    while (l < r) {
        ll mid = l + r >> 1;
        // printf("mid = %lld
", mid);
        if (ck(mid)) {
            r = mid;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '
';
    // system("pause");
}

完结撒花~~~

洛谷P1084 疫情控制

P1084 疫情控制 （二分+树上倍增+贪心）

题目描述

P1084 疫情控制（二分+树上倍增+贪心）