题解 P1084 【疫情控制】

看着下面的奆佬们都讲得差不多了，我来补充一些小细节。

（毒瘤的同志们可以对照着看看，这是一个晚上血与泪的教训）

1.关于贪心。

贪心前要判断一下，如果空闲军队数＜需要军队的城市数，则显然不行~
不要认为for中判得出来，事实证明并不能。

2.关于初始化。

1>记录军队的vector要在开始的时候弹空。
2>记录军队走过路径长度的（无论是数组还是变量）要在最开始清零。

3.关于精度

要开long long！
内存记住有的要开<<1。

额，有点抽象，可以结合代码看一看。
数组多而且千奇百怪，所以我给一些数组加了注释。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
struct Edge{int to,next;long long v;
}a[200001];
int h[100001],cnt;
int n,m;
void add(int x,int y,long long z)
{
    a[++cnt].to=y;
    a[cnt].v=z;
    a[cnt].next=h[x];
    h[x]=cnt;
}
int p[100001][20];
long long dis[100001][20];
void Dfs(int x)
{
    for(int i=h[x];i;i=a[i].next)
        if(!(~p[a[i].to][0])) p[a[i].to][0]=x,dis[a[i].to][0]=a[i].v,Dfs(a[i].to);
}
void ST()
{
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(~p[i][j-1]) p[i][j]=p[p[i][j-1]][j-1],dis[i][j]=dis[p[i][j-1]][j-1]+dis[i][j-1];
}
long long v[100001];
int g[100001]/*在不超过dat的情况下能到达的最浅节点(最大为1)*/;
int st[100001]/*在[]点有军驻扎(在第一次判断，即还未向其他节点移动时)*/;
long long t[100001]/*到g[]用时*/;
int H[100001],link[100001];
long long ar[100001],ci[100001];
vector<long long> army[100001];
bool Satisfied(int x)/*检查是否有足够检查站，是返回1，否返回0*/
{
    if(!H[x]&&st[x]) return 1;
    bool flag=0;
    for(int i=h[x];i;i=a[i].next)
        if(a[i].to!=p[x][0])
        {
            flag=1;
            if(!Satisfied(a[i].to)) return 0;
        }
    return flag;
}
bool Check(long long dat)
{
    for(int i=1;i<=H[0];i++)
        while(!army[i].empty()) army[i].pop_back();
    memset(st,0,sizeof(st));

    for(int i=1;i<=m;i++)
    {
        g[i]=v[i];
        t[i]=0;
        for(int j=18;j>=0;j--)
            if(~p[g[i]][j]&&p[g[i]][j]!=1&&t[i]+dis[g[i]][j]<=dat) t[i]+=dis[g[i]][j],g[i]=p[g[i]][j];
        st[g[i]]=1;
        if(H[g[i]])
        {
            int dh=H[g[i]];
            army[dh].push_back(dat-t[i]);
            int sh=army[dh].size();
            if(sh>1&&army[dh][sh-1]>army[dh][sh-2]) swap(army[dh][sh-1],army[dh][sh-2]);
        }
    }
    ar[0]=ci[0]=0;
    for(int i=1;i<=H[0];i++)
    {
        if(!Satisfied(a[link[i]].to))
            if((!army[i].empty())&&army[i][army[i].size()-1]<(a[link[i]].v<<1)) army[i].pop_back();
            else ci[++ci[0]]=a[link[i]].v;
        for(int j=0;j<army[i].size();j++)
            if(army[i][j]>=a[link[i]].v) ar[++ar[0]]=army[i][j]-a[link[i]].v;
    }
    sort(ar+1,ar+1+ar[0]);
    sort(ci+1,ci+1+ci[0]);
    if(ar[0]<ci[0]) return 0;
    for(int i=ar[0],j=ci[0];j;i--,j--)
        if(ar[i]<ci[j]) return 0;
    return 1;
}
int main()
{
    int x,y;
    long long z,sum=0;
    scanf("%d",&n);
    for(int i=1;i<n;i++) scanf("%d %d %lld",&x,&y,&z),add(x,y,z),add(y,x,z),sum+=z;
    memset(p,-1,sizeof(p));
    p[1][0]=0;
    Dfs(1);
    p[1][0]=-1;
    ST();
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%lld",&v[i]);
    for(int i=h[1];i;i=a[i].next) H[a[i].to]=++H[0],link[H[0]]=i;
    long long l=0,r=sum+1;
    while(l<r)
    {
        long long mid=l+r>>1;
        if(Check(mid)) r=mid;
        else l=mid+1;
    }
    if(l>sum) puts("-1");
    else printf("%lld\n",l);
    return 0;
}

实测：

#1 14ms/10.91MB AC
#2 628ms/23.24MB AC
#3 14ms/10.94MB AC
#4 14ms/10.95MB AC
#5 13ms/10.98MB AC
#6 17ms/11.06MB AC
#7 16ms/11.05MB AC
#8 18ms/12.87MB AC
#9 21ms/12.92MB AC
#10 13ms/11.03MB AC