[HOJ 79][POI 16 Stage 1] 滅人器

我的作法：




先隨便選一個點當根轉成有根樹，可以證明，如果有一個點沒被滅人器覆蓋到的話，那選他的k級組先放滅人器是最好的。

所以由深度深的點作到深度淺的，每次判斷有沒有滅人器覆蓋到這個點，沒有的話就在k級組先放，有的話就把那個滅人器的個數減一 。

另外還有一件蠻直覺的事，就是如果有滿足的滅人器的話，選深度最深的那個，但我不知道怎麼證明@@




所以可以想到第一種作法，每作一個點的時候對他DFS，看距離他 k 步以內有沒有滅人器，有的話就更新，找深度最深的，但這樣做是O(n^2)。




考慮每個點放了滅人器後，他自己有一個強度 k 的滅人器，他的 i 級組先等於有了一個強度 k-i 的滅人器，所以用個 set 記錄這個點擁有的強度 j 的滅人器有哪些，就可以在O(k^2)的時間內判斷有沒有滅人器覆蓋這個點。另外當然還是要選深度最深的，否則 8-2 測資會錯，獲得WA 90分 (?)

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
vector<int> v[maxn] ;
int fa[maxn] ;
 
struct P{int id,val;}a[maxn];
bool cmp(const P &a,const P &b)
{ return a.val==b.val ? a.id>b.id : a.val>b.val ; }
 
int d[maxn] ;
void dfs(int x,int dep)
{
    d[x]=dep ; a[x]=(P){x,dep} ;
 
    for(int i=0;i<v[x].size();i++) if(v[x][i]!=fa[x])
        fa[v[x][i]]=x , dfs(v[x][i],dep+1) ;
}
 
int cnt[maxn] ;
set<int> have[maxn][21] ;
main()
{
    int n,s,k ; scanf("%d%d%d",&n,&s,&k) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    fa[1]=1 ;
    dfs(1,0) ;
 
    sort(a+1,a+n+1,cmp) ;
    int ans=0 ;
    for(int i=1;i<=n;i++)
    {
        int x=a[i].id ;
 
        int found=-1,dep=-1 ;
        for(int j=0;j<=k;j++) if(have[x][j].size())
            { found=(*have[x][j].begin()) ; dep=d[found] ; break ; }
 
        int y=x ;
        for(int z=1;z<=k;z++)
        {
            y=fa[y] ;
            for(int j=z;j<=k;j++) if(have[y][j].size())
            {
                if(found==-1 || d[*have[y][j].begin()]>dep)
                    found=(*have[y][j].begin()) ,
                    dep = d[*have[y][j].begin()];
            }
        }
 
        if(found!=-1)
        {
            if(!(--cnt[found]))
                for(int z=0,j=found;z<=k;z++,j=fa[j])
                    have[j][k-z].erase(found) ;
            continue ;
        }
 
        cnt[y]=s-1 ; ans++ ;
        if(s==1) continue ;
 
        for(int z=0,j=y;z<=k;z++,j=fa[j])
            {have[j][k-z].insert(y) ; if(j==1) break ;}
    }
    printf("%d\n",ans) ;
}
 

另外，陳博彰給了個O(nk)的作法，作法是記錄這個點的子樹需要多少距離 i 的滅人器，和能提供多少距離 i 的滅人器，然後盡量晚配對(將需求與供給幾消)兩者。code如下：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
constexpr int max_n = 100000;
constexpr int max_k = 20;
 
int n, s, k;
vector<int> adj[max_n];
 
int supply[max_n][max_k + 1];
int demand[max_n][max_k + 1];
 
int dfs(int x, int p) {
    int extinguisher = 0;
    for(int c : adj[x])
        if(c != p) {
            extinguisher += dfs(c, x);
            for(int i = 0; i < k; i++) {
                supply[x][i] += supply[c][i + 1];
                if(supply[x][i] > n)
                    supply[x][i] = n;
                demand[x][i + 1] += demand[c][i];
            }
        }
 
    demand[x][0] = 1;
    supply[x][k] = (demand[x][k] + s - 1) / s * s;
    extinguisher += (demand[x][k] + s - 1) / s;
    for(int i = 0; i <= k; i++) {
        int c = min(supply[x][i], demand[x][i]);
        supply[x][i] -= c;
        demand[x][i] -= c;
    }
    for(int i = 0; i < k; i++) {
        int c = min(supply[x][i + 1], demand[x][i]);
        supply[x][i + 1] -= c;
        demand[x][i] -= c;
    }
 
    return extinguisher;
}
 
int main(){
    scanf("%d %d %d", &n, &s, &k);
    for(int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    int extinguisher = dfs(0, -1);
    for(int i = 0; i <= k; i++)
        for(int j = 0; j <= i; j++) {
            int c = min(supply[0][i], demand[0][j]);
            supply[0][i] -= c;
            demand[0][j] -= c;
        }
 
    extinguisher += (accumulate(demand[0], demand[0] + k + 1, 0) + s - 1) / s;
    printf("%d\n", extinguisher);
}