BZOJ 1517 [POI2006]Met 贪心

题意: 给定一棵树，，选择l条路径覆盖最多的点的个数是多少。 解析: 选择路径的代价相同显然考虑贪心。 首先我们可以按照拓扑关系把原图分层。 接下来我们考虑，对于每一层来说，我们显然最多选取2*l个点。 我们最终选的路径一定是l对叶子节点到另一个叶子节点异或是都选。 又每一个叶子节点一定由上一层的来，所以选叶子节点的话一定会覆盖其他层的点。 =-=噫 我知道我说的好乱。 结论是什么呢？ 对于每一层来说，对答案的贡献是min(2*l,num[dep]) num[dep]代表第dep层的节点个数。 求和即可。 您可以从可行性以及最优性两个角度来考虑一下。 代码:

;int head[N],cnt;int n,l;int in[N];int dep[N];int sum[N];struct node{int from,to,next;}edge[N<<1];void init(){memset(head,-1,sizeof(head));cnt=1;}void edgeadd(int from,int to){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}void topsort(){queue<int>q;for(int i=1;i<=n;i++){if(in[i]==1)dep[i]=1,q.push(i),sum[1]++;}while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int to=edge[i].to;in[to]–;if(in[to]==1){dep[to]=dep[u]+1;sum[dep[to]]++;q.push(to);}}}int ans=0;for(int i=1;sum[i];i++){ans+=min(sum[i],2*l);}printf(“%d\n”,ans);}int main(){init();scanf(“%d%d”,&n,&l);for(int i=1;i<n;i++){int x,y;scanf(“%d%d”,&x,&y);edgeadd(x,y);edgeadd(y,x);in[x]++,in[y]++;}topsort();}

学会宽容，要有一颗宽容的爱心！