【noip2012】疫情控制

题意：

给出一颗n个节点有边权的树和m个军队所在的位置军队从某节点移动到相邻节点要花费边长度的时间求最少要多少时间使得根节点（编号为1）到每个叶子的路径上最少有一支军队（根节点不能有军队）

题解：

我们可以二分答案那么问题就转换为在t的时间内军队能否控所有点

显然一支军队在到根节点之前如果能继续向上走那么这支军队能控制的点就会更多

维护bo[i]表示从该点到所有该点子树的叶子节点路径上是否都有军队

对于每个不能走到根节点的军队就让他尽量向上走直到不能走为止将该点的bo值赋为1 然后可以用拓扑算出bo数组

这样根节点的所有儿子中bo为1的点就不用管而剩下的点就需要派能走到根节点的军队到这些点控制

于是问题转换为有n0个点需要被控制且控制该点需要Li的时间还有m0支军队每支军队有ti的时间求这m0支军队是否能控制这n0个点

这原本这样将L和t分别排序贪心用两个指针一个个扫就行了

但是要注意的是如果军队j就是从i点走到首都的那么该军队不论有多少剩余时间都能控制该点（去年noip考试的时候好像就是没想到这点）

这个问题我们只要做一个小转换就行了如果i点有军队从该点到达首都那么用minarm[i]记下这些军队中剩余时间最少的是谁当指针扫到i时先判断minarm[i]是否被用过了如果没有那么用minarm[i]来控制i 否则再在j指针上找军队

证明：如果minarm[i]没被使用那么t[j]>=t[minarm[i]] 所以在i点如果用minarm[i]则能省下一个剩余时间更多的军队对于之后可能用到minarm[i]的点完全可以用j点代替

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using std::sort;

 const int N=;

 struct inli{

     int next,data,lon;

     inli(const int a=,const int b=,const int c=):

         next(a),data(b),lon(c){}

 }line[N*];

 struct info{

     int t,s;

     info(const int a=,const int b=):

         t(a),s(b){}

 }ar[N],ci[N];

 inline bool cmp(info a,info b){ return a.s>b.s; }

 int n,m,na,nc,fat[N],ti[N],gra[N],dis[N],arm[N],nl,son[N],mint[N],add,boo[N];

 int max(int x,int y){ return x>y ? x : y; }

 void dfs(int t){

     int res=-,bo1=,bo2=;

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t]){

         int ne=line[i].data;

         dfs(ne);

         if (ti[ne]==-) bo2=;

         if (ti[ne]-line[i].lon>=) bo1=;

         res=max(res,ti[ne]-line[i].lon);

     }

     if (t!= && line[son[t]].next){

         if (bo1) ti[t]=max(ti[t],res);

         else if (bo2) ti[t]=max(ti[t],-);

         else ti[t]=max(ti[t],);

     }

 }

 void maketi(int t){

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

     if (dis[arm[i]]>=t) ti[arm[i]]=t;

     dfs();

 }

 void makear(int t){

     na=;

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

     if (dis[arm[i]]<t) ar[++na]=info(gra[arm[i]],t-dis[arm[i]]);

     sort(ar+,ar+na+,cmp);

     for (int i=;i<=na;i++){

         int x=ar[i].t;

         if (mint[x]==) mint[x]=i;

         else if (ar[mint[x]].s>ar[i].s) mint[x]=i;

     }

 }

 void makeci(){

     nc=;

     for (int i=son[];i;i=line[i].next)

     if (ti[line[i].data]==-) ci[++nc]=info(line[i].data,line[i].lon);

     sort(ci+,ci+nc+,cmp);

 }

 bool work(){

     if (na<nc) return ;

     memset(boo,,sizeof(boo));

     for (int i=,j=;i<=nc;i++)

     if (!boo[mint[ci[i].t]] && mint[ci[i].t]) boo[mint[ci[i].t]]=;

     else{

         while (boo[j] && j<=na) ++j;

         if (j>na) return ;

         if (ar[j].s<ci[i].s) return ;

         boo[j++]=;

     }

     return ;

 }

 bool check(int t){

     memset(ti,-,sizeof(ti));

     memset(mint,,sizeof(mint));

     maketi(t);

     makear(t);

     makeci();

     return work();

 }

 int getans(){

     int l=-,r=,mid;

     while (l+<r){

         mid=(l+r)/;

         if (check(mid)) r=mid;

         else l=mid;

     }

     return r;

 }

 void makefat(int t){

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t]){

         int ne=line[i].data;

         if (t==) gra[ne]=ne;

         else gra[ne]=gra[t];

         fat[ne]=t;

         dis[ne]=dis[t]+line[i].lon;

         makefat(ne);

     }

 }

 int main(){

     freopen("blockade.in","r",stdin);

     freopen("blockade.out","w",stdout);

     scanf("%d",&n);

     for (int x,y,z,i=;i<n;i++){

         scanf("%d%d%d",&x,&y,&z);

         line[++nl]=inli(son[x],y,z),son[x]=nl;

         line[++nl]=inli(son[y],x,z),son[y]=nl;

         if (x== || y==) ++add;

     }

     makefat();

     scanf("%d",&m);

     if (m<add){

         printf("-1");

         return ;

     }

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

     sort(arm+,arm+m+);

     printf("%d",getans());

     fclose(stdin);

     fclose(stdout);

 }

巴特西

【noip2012】疫情控制

最新文章

热门文章