3279 奶牛健美操

USACO

 时间限制: 2 s
 空间限制: 256000 KB
 题目等级 : 钻石 Diamond
题目描述 Description

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 Description

* 第1行: 两个空格分隔的整数V和S

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

输出描述 Output Description

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

样例输入 Sample Input

7 2

6 7

3 4

6 5

1 2

3 2

4 5

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

对于50%的数据,满足V<=100;

对于100%的数据,满足V<=100000

/*二分答案+贪心求解*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+;
struct node
{
int v,next;
}t[N*];
int n,s,tot,ans,head[N];
int f[N],a[N];
void add(int x,int y)
{
t[++tot].v=y;
t[tot].next=head[x];
head[x]=tot;
}
void dfs(int u,int fa,int num)
{
int cnt=;
for (int i=head[u];i;i=t[i].next)
if (t[i].v!=fa)
dfs(t[i].v,u,num);
for (int i=head[u];i;i=t[i].next)
if (t[i].v!=fa)
a[++cnt]=f[t[i].v]+;
sort(a+,a+cnt+);
while (cnt&&a[cnt]+a[cnt-]>num)
{
cnt--;
ans++;
}
f[u]=a[cnt];
}
bool check(int x)
{
ans=;
dfs(,,x);
return ans<=s;
}
int main()
{
scanf("%d%d",&n,&s);
for (int i=,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
int l=,r=n;
while(l<r)
{
int mid=(l+r)/;
if (check(mid))
r=mid;
else
l=mid+;
}
printf("%d\n",l);
return ;
}

最新文章

  1. js 对象的_proto_
  2. 毕设1--利用Java实现网页的模板功能技术---简要了解
  3. HttpSession
  4. Windows Phone开发需要了解的背景
  5. Grpc微服务从零入门
  6. [转] Finding the Best Programmer&#39;s Font
  7. 十个JavaScript中易犯的小错误,你中了几枪?
  8. argparse - 命令行选项与参数解析(转)
  9. zoj1537- Playing with a Calculator
  10. XtraBackup应用说明(支持TokuDB)
  11. PS抠图简单粗暴2种方法
  12. Telegraf安装与介绍
  13. 扒一扒开源世界有哪些licenses?
  14. go中的读写锁RWMutex
  15. 【Luogu4723】线性递推(常系数齐次线性递推)
  16. Codeforces 1072 C - Cram Time
  17. 《算法》第四章部分程序 part 11
  18. 数组转xml格式/xml格式转数组
  19. _编程语言_C++_宏定义#define 和 常量const 的区别
  20. HTML5 manifest离线缓存技术

热门文章

  1. VC++深入详解读书笔记-第六章菜单
  2. WinForm(C#)自定义控件之——RoundButton(圆形按钮)
  3. django 自定用户系统 以及 Django Model 定义语法
  4. mybatis常用语句
  5. web标准(复习)--2 列布局
  6. Python学习笔记总结(四)异常处理
  7. 用js实现两个select下拉框之间的元素互相移动
  8. iOS 第三方 需要 引用的库
  9. Microsoft.Practices.Unity 给不同的对象注入不同的Logger
  10. Oracle 提示密码过期问题:the password will expire