疫情控制(codevs 1218)

题目描述 Description

H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，

也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境

城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境

城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，

首都是不能建立检查点的。

现在，在 H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军

队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在

一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等

于道路的长度（单位：小时）。

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

输入描述 Input Description

第一行一个整数 n，表示城市个数。

接下来的 n-1 行，每行 3 个整数，u、v、w，每两个整数之间用一个空格隔开，表示从

城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。

接下来一行一个整数 m，表示军队个数。

接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎

的城市的编号。

输出描述 Output Description

共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

样例输入 Sample Input

1 2 1

1 3 2

3 4 3

2 2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【输入输出样例说明】

第一支军队在 2 号点设立检查点，第二支军队从 2 号点移动到 3 号点设立检查点，所需

时间为 3 个小时。

【数据范围】

保证军队不会驻扎在首都。

对于 20%的数据，2≤ n≤ 10；

对于 40%的数据，2 ≤n≤50，0<w <10^5；

对于 60%的数据，2 ≤ n≤1000，0<w <10^6；

对于 80%的数据，2 ≤ n≤10,000；

对于 100%的数据，2≤m≤n≤50,000，0<w <10^9。

/*

  二分+倍增+贪心

  ①题目要求使最长时间最短，那我们会想到二分答案，二分出答案之后，

  要使各处的军队尽量向上跑才最优，因为这样能覆盖尽量多的点。

  ②对于能跑到根节点的点，我们就记录他跑到根节点后最多还能跑多远，

  并且记录下他是从根节点的哪那个子节点来的，这些信息都记录到b结构体中。

  ③对于那些跑不到根节点的军队，我们让他待在能跑到的最高处，而且进行一遍深搜，

  如果某个点的所有子节点都保证能覆盖，我们就认为它也能被覆盖。

  ④在根节点的子节点中找到没有被覆盖的，然后用b结构体中的军队来分配给他们，

  分配原则是:如果b结构体军队原来的点没有覆盖，就覆盖原来的，否则，从小到大一一对应。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define M 50010

using namespace std;

int head[M],pos[M],fa[M][],dis[M][],vis[M],n,m;

struct node{int v,pre,t;};node e[M*];

struct Node{int u,v;};Node b[M],c[M];

int read()

{

    char c=getchar();int num=,flag=;

    while(c<''||c>''){if(c=='-')flag=-;c=getchar();}

    while(c>=''&&c<=''){num=num*+c-'';c=getchar();}

    return num*flag;

}

void add(int i,int x,int y,int z)

{

    e[i].v=y;

    e[i].t=z;

    e[i].pre=head[x];

    head[x]=i;

}

bool cmp(const Node&x,const Node&y)

{

    return x.v<y.v;

}

void dfs(int now,int from)

{

    fa[now][]=from;

    for(int i=head[now];i;i=e[i].pre)

      if(e[i].v!=from)

      {

          dis[e[i].v][]=e[i].t;

          dfs(e[i].v,now);

      }

}

void get_fa()

{

    for(int j=;j<=;j++)

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

      {

          fa[i][j]=fa[fa[i][j-]][j-];

          dis[i][j]=dis[i][j-]+dis[fa[i][j-]][j-];

      }

}

void color(int x)

{

    bool p=,q=;

    for(int i=head[x];i;i=e[i].pre)

      if(e[i].v!=fa[x][])

      {

          color(e[i].v);p&=vis[e[i].v];q=;

      }

    if(p&&q&&x!=)vis[x]=;

}

bool check(int x)

{

    memset(vis,,sizeof(vis));

    int cnt=,tot=;

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

    {

        int y=pos[i],z=;

        for(int j=;j>=;j--)//尽量向上跑

          if(fa[y][j]&&z+dis[y][j]<=x)

          {

              z+=dis[y][j];

              y=fa[y][j];

          }

        if(y!=)vis[y]=;//跑不到根节点

        else//能跑到根节点，求出b结构体

        {

            b[++cnt].v=x-z;

            y=pos[i];

            for(int j=;j>=;j--)

              if(fa[y][j]>)

                y=fa[y][j];

            b[cnt].u=y;

        }

    }

    color();//处理跑不到根节点的点

    for(int i=head[];i;i=e[i].pre)//找根节点的子节点

      if(!vis[e[i].v])

      {

          c[++tot].u=e[i].v;

          c[tot].v=e[i].t;

      }

    sort(b+,b+cnt+,cmp);

    sort(c+,c+tot+,cmp);

    int j=;

    for(int i=;i<=cnt;i++)//匹配

    {

        if(!vis[b[i].u])vis[b[i].u]=;

        else if(b[i].v>=c[j].v)vis[c[j].u]=;

        while(vis[c[j].u]&&j<=tot)j++;

    }

    return j>tot;

}

int main()

{

    n=read();

    int ll=,rr=;

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

    {

        int x=read(),y=read(),z=read();

        add(i*-,x,y,z);add(i*,y,x,z);

        rr+=z;

    }

    m=read();

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

      pos[i]=read();

    dfs(,);//深搜记录父亲结点，边权值

    get_fa();//DP求出倍增用到的节点和权值

    while(ll<=rr)//二分答案

    {

        int mid=(ll+rr)/;

        if(check(mid))rr=mid-;

        else ll=mid+;

    }

    if(check(ll))printf("%d",ll);

    else printf("-1");

    return ;

}

巴特西

疫情控制(codevs 1218)

最新文章

热门文章