[Usaco2010 Dec]Exercise 奶牛健美操

题目

Farmer John为了保持奶牛们的健康，让可怜的奶牛们不停在牧场之间的小路上奔跑。这些奶牛的路径集合可以被表示成一个点集和一些连接两个顶点的双向路，使得每对点之间恰好有一条简单路径。简单的说来，这些点的布局就是一棵树，且每条边等长，都为1。对于给定的一个奶牛路径集合，精明的奶牛们会计算出任意点对路径的最大值，我们称之为这个路径集合的直径。如果直径太大，奶牛们就会拒绝锻炼。 Farmer John把每个点标记为1..V (2 <= V <= 100,000)。为了获得更加短的直径，他可以选择封锁一些已经存在的道路，这样就可以得到更多的路径集合，从而减小一些路径集合的直径。我们从一棵树开始，FJ可以选择封锁S (1 <= S <= V-1)条双向路，从而获得 S+1个路径集合。你要做的是计算出最佳的封锁方案，使得他得到的所有路径集合直径的最大值尽可能小。 Farmer John告诉你所有V-1条双向道路，每条表述为：顶点A_i (1 <= A_i <= V) 和 B_i (1 <= B_i <= V; A_i!= B_i)连接。我们来看看如下的例子：线性的路径集合(7个顶点的树) 1---2---3---4---5---6---7 如果FJ可以封锁两条道路，他可能的选择如下： 1---2 | 3---4 | 5---6---7 这样最长的直径是2，即是最优答案(当然不是唯一的)。

INPUT

第1行：两个空格分隔的整数V和S * 第2...V行：两个空格分隔的整数A_i和B_i

OUTPUT

第1行：一个整数，表示FJ可以获得的最大的直径。

SAMPLE

INPUT

7 2

6 7

3 4

6 5

1 2

3 2

4 5

OUTPUT

2

解题报告

二分答案$+$贪心验证，竟然放在$DP$专题里= =（可能是我造化不够）

首先我们可以看到题面中闪闪发光的一句话

最大值尽可能小

这东西一眼看上去就知道，二分差不多就是可行的了

我们可以二分该最小值，然后验证其是否合法

我们设$f[i]$表示以第$i$个节点为根的子树中，合法的最长直链的长度

合法：

即保证最长链长度不可大于二分的答案

直链：

指链两端点路径不跨过根节点的链

然后我们就可以用$f[i]$计算要砍去多少条边，从而判断当前二分出的答案的合法性

那么问题来了，如何计算$f[i]$

显然直接求$max(f[son])$是不可行的，因为这不保证合法，但我们想，当我们选出两条儿子所在的直链，发现当他们接在一起时长度过大，需要从中砍断的时候，会有这样的事情：

砍较长链链顶的边最优
砍完该边后，该链不再对父节点造成影响

第二点显然，砍完之后该链与父节点不再属于同一联通块内，故不会再影响

第一点也很显然（废话），如果我们砍较短链，或者不是链顶的边，那么最长直链可能还会与其他直链相接再次产生不合法链，需要多砍一次，所以砍较长链链顶的边是最优的

那么我们就可以处理了，将当前节点的所有$f[son]$从大到小排序，依次枚举，判断相邻的两条直链长度相接是否合法，假如合法，将$f[i]$赋值，否则继续枚举，并且记录砍掉的边的数目$++$

注意处理某些奇怪的边界问题

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 inline int read(){

     int sum();

     char ch(getchar());

     for(;ch<''||ch>'';ch=getchar());

     for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());

     return sum;

 }

 struct edge{

     int e;

     edge *n;

 }a[],*pre[];

 int tot;

 inline void insert(int s,int e){

     a[++tot].e=e;

     a[tot].n=pre[s];

     pre[s]=&a[tot];

 }

 int n,m;

 int f[],fa[];

 int ans;

 int mid,num;

 int tmp[];

 inline bool cmp(int x,int y){

     return x>y;

 }

 inline void dfs(int u){

     bool flag(false);

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);

         if(e!=fa[u]){

             flag=true;

             fa[e]=u;

             dfs(e);

         }

     }

     if(!flag)

         return;

     tmp[]=;

     f[u]=;

     for(edge *i=pre[u];i;i=i->n){

         int e(i->e);

         if(e!=fa[u])

             tmp[++tmp[]]=f[e]+;

     }

     int size(tmp[]);

     sort(tmp+,tmp++size,cmp);

     tmp[size+]=;

     for(int i=;i<=size;++i){

         if(tmp[i]+tmp[i+]>mid)

             ++num;

         else{

             f[u]=tmp[i];

             break;

         }

     }

 }

 inline bool check(){

     num=;

     memset(f,,sizeof(f));

     dfs();

     if(num<=m)

         return true;

     return false;

 }

 inline void ef(int l,int r){

     while(l<=r){

         mid=(l+r)>>;

         if(check())

             r=mid-,ans=mid;

         else

             l=mid+;

     }

 }

 int main(){

     memset(pre,NULL,sizeof(pre));

     n=read(),m=read();

     for(int i=;i<n;++i){

         int x(read()),y(read());

         insert(x,y),insert(y,x);

     }

     ef(,n);

     printf("%d",ans);

 }

巴特西

[Usaco2010 Dec]Exercise 奶牛健美操

[Usaco2010 Dec]Exercise 奶牛健美操

题目

INPUT

OUTPUT

SAMPLE

INPUT

OUTPUT

解题报告

最新文章

热门文章