题解 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
查看7道真题和解析