Pro

??GAS gastask

? 給出一個n個節(jié)點的樹，現(xiàn)在要在這棵樹上放置一些指示物：

? 1.?????? 一個節(jié)點可以放置多個指示物；

? 2.?????? 一個指示物擁有一個籠罩范圍，即與它本身所在節(jié)點的距離在k個節(jié)點之內(nèi)的任何節(jié)點，它都可以選擇籠罩

? 3.?????? 每個指示物最多籠罩s個不同的節(jié)點。

? 問題是使用最少的指示物將整棵樹全部籠罩到。

Solution

題目給出了一棵樹，可以比較容易地得到對于一個節(jié)點，我們找到一個從它這里可以覆蓋到的最遠(yuǎn)的子節(jié)點，那么從它到這個子節(jié)點的路徑上的每一個節(jié)點設(shè)立指示物都可以覆蓋到這個子節(jié)點，那么從當(dāng)前的這個節(jié)點設(shè)立應(yīng)該是最優(yōu)的，這樣有沒有可能有反例呢？

我們假設(shè)這條路徑中有某一個節(jié)點i的子樹中有另一個節(jié)點j，這個節(jié)點是i可以到達而之前的那個祖先節(jié)點所無法到達的，那么這個時候就有可能出現(xiàn)在節(jié)點i設(shè)立指示物比在祖先節(jié)點設(shè)立更優(yōu)的情況（想想就知道），這就出現(xiàn)了反例。

為了避免這種情況，我們可以每次找深度最大的一個葉子節(jié)點，然后再找離它最遠(yuǎn)的祖先節(jié)點作為覆蓋它的節(jié)點，那么就可以保證這樣的決策不會出現(xiàn)上面的反例。

由于最深的節(jié)點滿足拓?fù)湫?#xff0c;所以可以使用一個隊列來維護，對于每一個節(jié)點查詢覆蓋節(jié)點。整個算法的復(fù)雜度為O（nk）。

不過這樣實現(xiàn)起來比較麻煩，這里我學(xué)到了一個來自濤哥的方法：我們使用f[i][j]表示從i號節(jié)點向子樹中深搜j步所能到達的節(jié)點個數(shù)，g[i][j]表示從i號向子樹中深搜j步所能到達的節(jié)點現(xiàn)在設(shè)立的指示物還能覆蓋多少節(jié)點（有點繞）。

我們先深度遍歷每一個點，然后遞歸處理出每個點能覆蓋它的子樹的節(jié)點個數(shù)最大是多少，由于這樣是最優(yōu)的所以我們在這個節(jié)點設(shè)立相應(yīng)的指示物來覆蓋它們，同時更新還能覆蓋的節(jié)點個數(shù)，然后我們還要更新覆蓋點和被覆蓋點都在當(dāng)前節(jié)點子樹中的情況，即跨立的情況，如果子樹中有某一個節(jié)點可以到達子樹中的另外一個點并且其當(dāng)先設(shè)立的指示物還能繼續(xù)覆蓋點，那么就把這些點覆蓋。這樣深搜完之后，再在外面做一遍非最優(yōu)的決策看還有什么沒有被調(diào)整到的。

#include <stdio.h> #include <memory.h>const int nmax = 100000, kmax = 20;int n, k, s, f[nmax + 18][kmax + 18], g[nmax + 18][kmax + 18]; int fst[nmax + 18], pnt[(nmax << 1)+ 18], nxt[(nmax << 1)+ 18], tot = 0, ans = 0; bool ed[nmax + 18];void addedge (int s, int t) {pnt[++tot] = t;nxt[tot] = fst[s];fst[s] = tot;pnt[++tot] = s;nxt[tot] = fst[t];fst[t] = tot; }int top (int x) {return x ? (x - 1) / s + 1 : 0; }void adjust (int &a, int &b) {if (a >= b) a -= b, b = 0;else b -= a, a = 0; }void dfs (int i) {ed[i] = true;for (int kk = fst[i], j = pnt[kk]; kk; kk = nxt[kk], j = pnt[kk])if (!ed[j]){dfs (j);for (int l = 1; l <= k; ++l){f[i][l] += f[j][l - 1];g[i][l] += g[j][l - 1];g[i][l] <?= n;}}ans += top (f[i][k]);f[i][0] = 1;g[i][0] = top (f[i][k]) * s;for (int j = k; j >= 0; --j){adjust (f[i][k - j], g[i][j]);if (j < k) adjust (f[i][k - j - 1], g[i][j]);} }int main () {freopen ("gas.in", "r", stdin);freopen ("gas.out", "w", stdout);scanf ("%d%d%d", &n, &s, &k);for (int i = 1, s, t; i < n; ++i)scanf ("%d%d", &s, &t), addedge (s, t);dfs (1);for (int i = k; i >= 0; --i)for (int j = k - i; j >= 0; --j)adjust (f[1][j], g[1][i]);int S = 0;for (int i = 0; i <= k; ++i)S += f[1][i];printf ("%d", ans + top (S));return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Neroysq/archive/2011/08/19/2145412.html

總結(jié)

以上是生活随笔為你收集整理的[POI 2009] gas 贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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