初始數組忘了賦初值，，，我真是個機靈鬼

還有這題是三倍經驗P2279&&P2016，這題的實現思想來自P2279首個題解

---

?

luogu

簡化題意

給你一棵樹，你有一些可以覆蓋范圍為$k$的障礙物，問最少放幾個障礙物可以使樹上所有節點覆蓋

思想

這題貪心的思路其他題解寫的十分清楚。首先，每一次選的點不和之前選的點所覆蓋的區間重合，否則不優（這點很顯然），所以我們每次可以找到一個最低的點，選取它的第K級祖先來覆蓋這個點。$ta$和$ta$的祖先之間就標記為已覆蓋

代碼實現講解

實現難點在判斷該點是否被覆蓋，每個點被覆蓋的情況有三種

• 被自己的孩子所覆蓋
  • 此時直接在$ta$的孩子建立時就標記
• 被自己的祖先所覆蓋
  • 開一個數組${fa[]}$去記錄
• 被自己的兄弟所覆蓋
  • 開一個數組${dis[i]}$表示離$i$最近的障礙物離$i$的距離，當${dis[fa[i]]==k-1}$時，我們就可以確定，$i$肯定就會被覆蓋

每次在放置完障礙物之后，還要記得更新${dis[]}$的值

順便一提，這種方法的普適性很強，可以解決半徑為k的最小覆蓋問題。而且不用存圖。只需要把維護“父親和爺爺”改成維護“上位k位祖先”即可，復雜度O(N*K)，常數也很小。————BJpers2

這題的代碼實現就是這句話的延申

代碼實現

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int maxn=1e6+10; 7 struct ziji{int id,dep;}mn[maxn]; 8 #define id(i) mn[i].id 9 #define dep(i) mn[i].dep 10 int n,k,t,fa[maxn],dis[maxn],ans,tot; 11 int head[maxn],ver[maxn<<1],nxt[maxn<<1]; 12 inline bool cmp(ziji a,ziji b){ 13 return a.dep>b.dep; 14 } 15 inline int g() { register int x=0,f=1; 16 register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f; 17 do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f; 18 } 19 inline void add(int x,int y){ 20 ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; 21 } 22 inline void dfs(int x,int f){ 23 dep(x)=dep(f)+1;fa[x]=f; 24 for(register int i=head[x];i;i=nxt[i]){ 25 int y=ver[i];if(y==f) continue;dfs(y,x); 26 } 27 } 28 int main(){ 29 n=g(),k=g(),t=g(); 30 id(1)=1,dis[0]=dis[1]=maxn; 31 for(register int i=1;i<=n;i++) id(i)=i; 32 memset(dis,0x3f,sizeof(dis)); 33 for(register int i=2;i<=n;i++){ 34 int x,y;x=g(),y=g(); 35 add(x,y),add(y,x); 36 }dfs(1,1); 37 sort(mn+1,mn+1+n,cmp); 38 for(register int i=1;i<=n;i++){ 39 int x=id(i),y=x; 40 for(register int j=1;j<=k;j++) 41 y=fa[y],dis[x]=min(dis[x],dis[y]+j); 42 if(dis[x]>k){ 43 dis[y]=0,ans++; 44 for(register int j=1;j<=k;j++) 45 y=fa[y],dis[y]=min(dis[y],j); 46 } 47 } 48 printf("%d",ans); 49 } View Code

?

轉載于:https://www.cnblogs.com/fallen-down/p/11577534.html

總結

以上是生活随笔為你收集整理的题解P3942_将军令的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。