原文鏈接https://www.cnblogs.com/zhouzhendong/p/BZOJ1117.html

題目傳送門 - BZOJ1117

題意

　　給你一棵樹，現(xiàn)在要建立一些消防站，有以下要求:

　　　　1. 消防站要建立在節(jié)點(diǎn)上，每個(gè)節(jié)點(diǎn)可能建立不只一個(gè)消防站。

　　　　2. 每個(gè)節(jié)點(diǎn)應(yīng)該被一個(gè)消防站管理，這個(gè)消防站不一定建立在該節(jié)點(diǎn)上。

　　　　3. 每個(gè)消防站可以管理至多s個(gè)節(jié)點(diǎn)。

　　　　4. 消防站只能管理距離（兩點(diǎn)間最短路徑的邊數(shù)）不超過k的結(jié)點(diǎn)。

　　請(qǐng)問至少要設(shè)立多少個(gè)消防站。

題解

　　考慮貪心從下往上走。

　　設(shè) rem[x][i] 表示 x 的子樹中與 x 的距離為 i 的未決策節(jié)點(diǎn)總數(shù)。

　　設(shè) foc[x][i] 表示 x 的子樹中與 x 的距離為 i 的滅火器還能管轄多少節(jié)點(diǎn)。

　　貪心策略就是盡量把滅火器往祖先上應(yīng)用。

　　分兩個(gè)情況再描述一下：

　　1.　對(duì)于 rem[x][k] 這一部分，我們需要在節(jié)點(diǎn) x 新增滅火器。

　　2.　i 從小到大檢驗(yàn) foc[x][i] ，如果它可以滅 rem[x][i] 或者 rem[x][i-1] ，那么必然滅了最好，否則到上面了就滅不了了；就算別的滅火器滅了它，我們只需要交換這兩個(gè)滅火器的消滅對(duì)象就可以打到至少不劣的效果。

?

代碼

#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=100005,K=25; int read(){int x=0;char ch=getchar();while (!isdigit(ch))ch=getchar();while (isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x; } struct Graph{static const int M=N*2;int cnt,y[M],nxt[M],fst[N];void clear(){cnt=1;memset(fst,0,sizeof fst);}void add(int a,int b){y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;} }g; int n,s,k; LL rem[N][K],foc[N][K]; int ans=0; void solve(int x,int pre){rem[x][0]++;for (int i=g.fst[x];i;i=g.nxt[i])if (g.y[i]!=pre){int y=g.y[i];solve(y,x);for (int j=0;j<k;j++){rem[x][j+1]+=rem[y][j];foc[x][j]+=foc[y][j+1];}}int d=(rem[x][k]+s-1)/s;ans+=d;foc[x][k]+=d*s;for (int i=0;i<=k;i++)for (int j=i;foc[x][i]&&j>=0&&(j>=i-1||x==1);j--){d=min(foc[x][i],rem[x][j]);foc[x][i]-=d;rem[x][j]-=d;} } int main(){n=read(),s=read(),k=read();g.clear();for (int i=1;i<n;i++){int a=read(),b=read();g.add(a,b);g.add(b,a);}solve(1,0);int t=0;for (int i=0;i<=k;i++)t+=rem[1][i];printf("%d\n",ans+(t+s-1)/s);return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/zhouzhendong/p/BZOJ1117.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1117 [POI2009]救火站Gas 贪心的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。