消防局的设立将军令//贪心

本文主要是介绍消防局的设立将军令//贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

消防局有DP做法，而且要是按省选难度看的话那个题应该是DP

昨天跟冯神讨论了一下，如果点上设权，那么就只能DP做了

下面DP部分的详细讲解转载自luogu CaptainSlow 的题解（这里是他的博客）

DP[i][state] 表示 i 当前子树根节点
state就是一个一个的状态
state = 0, 1, 2 :
DP[i][0] 表示 选 i 为消防局
DP[i][1] 表示 {至少} 选了 i 的一个儿子为消防局 DP[i][2] 表示 {至少} 选了 i 的一个孙子为消防局 ==================================以上三种状态是 i {一定被消防局覆盖} 的情况 state = 3, 4 : DP[i][3] 表示 i 的 {所有} 儿子节点一定被消防局覆盖 DP[i][4] 表示 i 的 {所有} 孙子节点一定被消防局覆盖 ==================================以上两种状态是 i {不一定被消防局覆盖} 的情况

（以下j, k均表示i的儿子节点）
DP[i][0] = 1 + Σ min ( DP[j][0...4] );由于当 i 为消防站之后儿子和孙子是否为消防局就无关紧要，因此状态在0~4中寻找一个MIN，然后还需要+1（因为自己是消防局） DP[i][1] = min ( DP[k][0] + Σ ( j != k ) min ( DP[j][0...3] ) ); 由于儿子为消防站时只能覆盖到兄弟（这里不含所选儿子的儿子），要使选了一个儿子之后子树中包括自己的所有节点都被覆盖，所以除了这个选的儿子，其他儿子的儿子一定要全部被覆盖，状态0~3满足。 DP[i][2] = min ( DP[k][1] + Σ ( j != k ) min ( DP[j][0...2] ) ); 要使选了一个孙子之后合法，由于孙子最多只能覆盖到当前节点，所以其他儿子一定全部覆盖， 状态0~2满足 DP[i][3] = Σ min(DP[j][0...2]); 要使儿子及孙子全部被覆盖，即儿子本身要被覆盖，状态0~2满足 DP[i][4] = Σ min(DP[j][0...3]); 孙子全部被覆盖 ，状态0~3满足

加速：令 DP[i][j] 表示 min ( DP[i][0..k] ) (2<=k<=4)因此可以得到：DP[i][0] = 1 + Σ DP[j][4]; DP[i][1] = DP[i][4] + min ( DP[k][0] - DP[k][3] ); DP[i][2] = DP[i][3] + min ( DP[k][1] - DP[k][2] ); DP[i][3] = Σ DP[j][2]; DP[i][4] = Σ DP[j][3];

正确DP很神，很难设计状态，不太可做

我们可以口胡一个贪心，照样可以A这道题

我们随便pick一个点为根，然后算出每个点的深度

由于深度最深的点必须被覆盖，所以想到覆盖掉它的最好位置就是它的爷爷

为什么不是它的兄弟？因为你是最深的点，设在你的爷爷上必能覆盖你的兄弟，

但是设在兄弟上覆盖不到爷爷的爷爷，从正确性上讲，贪心得到证明

每次用优先队列找深度最大的点

AC代码：

#include<bits/stdc++.h>using namespace std ;const int MAXN = 1010;
struct Edge{int nxt,to;
}edge[MAXN<<1];
int head[MAXN],ectr;
void addedge(int from,int to){edge[++ectr].to = to;edge[ectr].nxt = head[from];head[from] = ectr;
}
int n,dep[MAXN],father[MAXN],book[MAXN];
struct Node{int ID,dep;
};
priority_queue<Node> q;
bool operator < (Node a,Node b){return a.dep < b.dep;
}void dfs1(int x,int fa){dep[x] = dep[fa] + 1;father[x] = fa;for(int i=head[x];i;i=edge[i].nxt){int to = edge[i].to;if(to == fa) continue;dfs1(to,x);}
}int find (int x,int now){if(x == 1 || now == 0) return x;else return find(father[x],now-1);
}void tatoo(int x,int fa,int now){book[x] = true;if(now == 0) return;for(int i=head[x]; i; i=edge[i].nxt){int to = edge[i].to;if(to == fa) continue;tatoo(to, x, now - 1);}
}int main(){cin>>n;for(int i=2;i<=n;++i){int aa;cin>>aa;addedge(aa,i);addedge(i,aa);}for(int i=head[1]; i; i=edge[i].nxt){int to = edge[i].to;dfs1(to,1);}for(int i=1;i<=n;i++){Node xxx;xxx.ID = i;xxx.dep = dep[i];q.push(xxx);}long long ans = 0;while(!q.empty()){Node xxx = q.top();q.pop();if(book[xxx.ID]) continue;++ans;int se = find(xxx.ID,2);
//        cout<<"ans = "<<ans<<" se = "<<se<<endl;tatoo(se,-1,2);}cout<<ans<<endl;return 0;
}

　　同时有一道同做法的题，而且只能贪心，叫将军令

　　这里贴出AC代码，跟上面差了几个变量名的事

#include<bits/stdc++.h>using namespace std ;const int MAXN = 100010;
struct Edge{int nxt,to;
}edge[MAXN<<1];
int head[MAXN],ectr;
void addedge(int from,int to){edge[++ectr].to = to;edge[ectr].nxt = head[from];head[from] = ectr;
}
int n,k,t,dep[MAXN],father[MAXN],book[MAXN];
struct Node{int ID,dep;
};
priority_queue<Node> q;
bool operator < (Node a,Node b){return a.dep<b.dep;
}void dfs1(int x,int fa){dep[x] = dep[fa] + 1;father[x] = fa;for(int i=head[x];i;i=edge[i].nxt){int to = edge[i].to;if(to == fa) continue;dfs1(to,x);}
}int find (int x,int now){if(x == 1 || now == 0) return x;else return find(father[x],now-1);
}void tatoo(int x,int fa,int now){book[x] = true;if(now == 0) return;for(int i=head[x];i;i=edge[i].nxt){int to = edge[i].to;if(to == fa) continue;tatoo(to, x, now - 1);}
}int main(){cin>>n>>k>>t;for(int i=1;i<n;++i){int a,b;cin>>a>>b;addedge(a,b);addedge(b,a);}for(int i=head[1];i;i=edge[i].nxt){int to = edge[i].to;dfs1(to,1);}for(int i=1;i<=n;i++){Node xxx;xxx.ID = i;xxx.dep = dep[i];q.push(xxx);}long long ans = 0;while(!q.empty()){Node xxx = q.top();q.pop();if(book[xxx.ID]) continue;++ans;int se = find(xxx.ID,k);tatoo(se,-1,k);}
//    cout<<find(3,1);cout<<ans<<endl;return 0;
}