[BZOJ1117]救火站gas

2023-07-20 08:06:34

Description

给你一棵树，现在要建立一些消防站，有以下要求: 1. 消防站要建立在节点上，每个节点可能建立不只一个消防站。 2. 每个节点应该被一个消防站管理，这个消防站不一定建立在该节点上。 3. 每个消防站可以管理至多s个节点。 4. 消防站只能管理距离（两点间最短路径的边数）不超过k的结点。请问至少要设立多少个消防站。

Input

第一行n,s,k。接下来n-1行每行xi,yi描述一条边连接xi与yi。 1<=n<=100000 1<=s<=n 1<=k<=20 1<=xi

Output

一个数，最少的消防站个数。

Sample Input

12 3 1
1 12
3 8
7 8
8 9
2 12
10 12
9 12
4 8
5 8
8 11
6 8

Sample Output

HINT

感谢MT大牛贡献译文.

Source

又是树上管理类的问题，我们当然考虑贪心。这个题算是消防站的设立那道题的加强版。

很显然的一种做法是对于一个点，我们要找一个深度最小的点来覆盖它。

然后看这个数据范围k<=20，我们可以想到把他当成状态放进数组里

设need[i][j]为以i为子树的j级子孙有几个未覆盖，left[i][j]为以i为子树的j级子孙有几个多出来控制的没使用

显然当need[i][j]中j=k时，我们就必须放消防站来管理了

然后我们还可以用left来抵消need

总之就是一道很巧妙的贪心题

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define M 100010

 #define ll long long

 using namespace std;

 struct point{

     int next,to;

 }e[M<<];

 int n,m,s,k,num;

 int head[M],fa[M];

 ll tot,ans;

 ll need[M][],lef[M][];

 void add(int from,int to)

 {

     e[++num].next=head[from];

     e[num].to=to;

     head[from]=num;

 }

 void dfs(int x,int f)

 {

     fa[x]=f; need[x][]=;

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

     {

         int to=e[i].to;

         if(to==fa[x]) continue;

         dfs(to,x);

         for(int j=;j<=k;j++) need[x][j]+=need[to][j-];

         for(int j=k-;j>=;j--) lef[x][j]+=lef[to][j+];

     }

     ll tmp=(need[x][k]+s-)/s;

     ans+=tmp;

     lef[x][k]+=(ll)tmp*s;

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

     {

         if(lef[x][i])

         {

             for(int j=i;j>=&&(j>=i-||x==);j--)

             {

                 if(lef[x][i]<=need[x][j])

                 {

                     need[x][j]-=lef[x][i];

                     lef[x][i]=;

                     break;

                 }

                 lef[x][i]-=need[x][j];

                 need[x][j]=;

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&s,&k);

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

     {

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

         add(x,y); add(y,x);

     }

     dfs(,);

     for(int i=;i<=k;i++) tot+=need[][i];

     ans+=(tot+s-)/s;

     printf("%lld",ans);

     return ;

 }

码农公寓