[BZOJ2097][Usaco2010 Dec]Exercise 奶牛健美操（二分+树形dp+贪心）

题目描述

传送门

题解

这什么dp啊？本质就是个贪心嘛。。。 最大值最小，很容易想到二分。关键是判定怎么判。 我们可以采取贪心的策略，也就是说，如果一条链长度大于mid的话就讲中间的一条边砍去。由于dfs的时候由下到上都保证了最长链长度小于或等于mid，那么每次一定不会砍掉多于一条边。 当dfs到点x的时候，我们已经算出来了点x的儿子到它的子树里的最长链f[son[x]]，将这所有的链从大到小排个序，然后判断i和i+1，如果大于mid的话就砍掉一条边（我们可以认为砍掉的就是x连向它儿子的那条边）。然后都砍完了之后新算出来的最大值就可以作为f[x]。 这个贪心的正确性直接证是不大好证明的，不过试一试就会知道无论链是什么情况都是合适的。

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 100005 int n,m,x,y,cnt,ans; int tot,point[N],nxt[N*2],v[N*2]; int a[N],f[N]; void addedge(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; } int cmp(int a,int b) { return a>b; } void treedp(int x,int fa,int limit) { f[x]=0; bool flag=false; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { flag=true; treedp(v[i],x,limit); if (f[v[i]]+1>f[x]) f[x]=f[v[i]]+1; } if (!flag) {f[x]=0;return;} a[0]=0; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) a[++a[0]]=f[v[i]]+1; sort(a+1,a+a[0]+1,cmp); for (int i=1;i<a[0];++i) if (a[i]+a[i+1]>limit) cnt++,a[i]=0; if (a[a[0]]>limit) cnt++,a[a[0]]=0; sort(a+1,a+a[0]+1,cmp); f[x]=a[1]/*,g[x]=a[2]*/; } int calc(int limit) { cnt=0; treedp(1,0,limit); return cnt; } int find() { int l=0,r=n-1,mid,ans; while (l<=r) { int mid=(l+r)>>1; if (calc(mid)<=m) ans=mid,r=mid-1; else l=mid+1; } return ans; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); addedge(x,y); } ans=find(); printf("%d\n",ans); }

总结

①要胆够大，心够细。——lxy