基础算法（二分，贪心）：NOIP 2012 疫情控制

题目大意

　　给出一棵n个节点的树，根是1，要在除根节点以外的点建立检查点，使得从每条根到叶子的路径上都至少存在一个检查点。检查点由军队来建立。初始军队的位置是给定的，移动军队走一条边需要花费这条边的权值的时间。现在要求一个方案，移动军队到某个最佳位置，使得总用时最少。

【数据范围】
保证军队不会驻扎在首都。
对于20%的数据，2≤ n≤ 10；
对于40%的数据，2 ≤n≤50，0<w <10⁵；
对于60%的数据，2 ≤ n≤1000，0<w <10⁶；
对于80%的数据，2 ≤ n≤10,000；
对于100%的数据，2≤m≤n≤50,000，0<w <10⁹。

　　这道题目没有想象的那样难，先是二分答案，再用倍增，接着树形dp，然后是贪心地分配判断是否合法。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <vector>
  6 using namespace std;
  7 typedef long long LL;
  8 const LL INF=1ll<<50;
  9 const int N=50010,D=17;
 10 int cnt,fir[N],nxt[N*2];
 11 int to[N*2];LL val[N*2];
 12 LL dis[D][N],fa[D][N];
 13 void addedge(register int a,register int b,LL w){
 14   nxt[++cnt]=fir[a];
 15   fir[a]=cnt;
 16   val[cnt]=w;
 17   to[cnt]=b;
 18 }
 19 int n,m,dep[N];
 20 void Prepare(){
 21   for(register int k=1;k<=16;k++)
 22     for(register int i=1;i<=n;i++){
 23       fa[k][i]=fa[k-1][fa[k-1][i]];
 24       dis[k][i]=dis[k-1][i]+dis[k-1][fa[k-1][i]];
 25     }
 26 }
 27 void DFS(register int x){
 28   for(register int i=fir[x];i;i=nxt[i])
 29     if(to[i]!=fa[0][x]){
 30       fa[0][to[i]]=x;
 31       dep[to[i]]=dep[x]+1;
 32       dis[0][to[i]]=val[i];
 33       DFS(to[i]);
 34     }
 35 }
 36 int dp[N],st[N];
 37 vector<LL>v[N];
 38 void DP(register int x){
 39   if(dep[x]>1)
 40     dp[x]=v[x].size();
 41   else dp[x]=0;
 42   bool tmp=true,flag=false;
 43   for(register int i=fir[x];i;i=nxt[i])
 44     if(to[i]!=fa[0][x]){
 45       DP(to[i]);
 46       tmp&=dp[to[i]];
 47       flag=true;
 48     }
 49   dp[x]|=tmp&flag;
 50 }
 51 int ca,cb,p[N];
 52 LL a[N],b[N],c[N];
 53 bool Check(LL mid){
 54   for(register int i=1;i<=n;i++)
 55     v[i].clear();
 56   for(register int i=1;i<=m;i++){
 57     LL tmp=mid;register int x=st[i];
 58     for(register int k=16;k>=0;k--)
 59       if(dis[k][x]<=tmp){
 60           if(fa[k][x]<=1)continue;
 61     tmp-=dis[k][x];
 62     x=fa[k][x];
 63       }
 64     v[x].push_back(tmp);
 65   }
 66   DP(1);ca=cb=0;
 67   for(register int i=fir[1],y;i;i=nxt[i]){
 68     register int sz=v[y=to[i]].size(),z=0;
 69     if(!dp[y])b[++cb]=val[i],z=cb;
 70     for(register int j=0;j<sz;j++){
 71       a[++ca]=v[y][j]-val[i];
 72       c[ca]=z;
 73     }
 74   }
 75   memset(p,0,sizeof(p));
 76   for(register int i=1;i<=ca;i++){
 77     if(!p[c[i]])p[c[i]]=i;
 78     else if(a[p[c[i]]]>a[i])
 79       p[c[i]]=i;
 80   }
 81   for(register int i=1;i<=cb;i++)
 82     if(p[i]&&b[i]>a[p[i]]){
 83       b[i]=a[p[i]]=INF;
 84     }
 85   sort(a+1,a+ca+1);while(a[ca]==INF)ca--;
 86   sort(b+1,b+cb+1);while(b[cb]==INF)cb--;
 87   for(register int i=1,j=1;i<=ca;i++){
 88     if(a[i]>=b[j])j++;
 89     if(j>cb)return true;
 90   }
 91   return false;
 92 }
 93 
 94 
 95 LL l,r,mid,w;
 96 int main(){
 97   freopen("blockade.in","r",stdin);
 98   freopen("blockade.out","w",stdout);
 99   scanf("%d",&n);
100   for(register int i=1,a,b;i<n;i++){
101     scanf("%d%d%lld",&a,&b,&w);
102     addedge(a,b,w);
103     addedge(b,a,w);
104   }DFS(1);Prepare();
105   scanf("%d",&m);
106   for(register int i=1;i<=m;i++)
107     scanf("%d",&st[i]);
108   l=0;r=INF;
109   while(l<=r){
110     mid=(l+r)>>1;
111     if(Check(mid))r=mid-1;
112     else l=mid+1;
113   }
114   if(l>INF)l=-1;
115   printf("%lld
",l);
116   return 0;
117 }

基础算法（二分，贪心）：NOIP 2012 疫情控制

题目大意

相关推荐