CODEVS 3279 奶牛的健美操
3279 奶牛健美操
USACO
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,即是最优答案(当然不是唯一的)。
* 第1行: 两个空格分隔的整数V和S
* 第2...V行: 两个空格分隔的整数A_i和B_i
* 第1行:一个整数,表示FJ可以获得的最大的直径。
7 2
6 7
3 4
6 5
1 2
3 2
4 5
2
对于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 ;
}
最新文章
- js 对象的_proto_
- 毕设1--利用Java实现网页的模板功能技术---简要了解
- HttpSession
- Windows Phone开发需要了解的背景
- Grpc微服务从零入门
- [转] Finding the Best Programmer&#39;s Font
- 十个JavaScript中易犯的小错误,你中了几枪?
- argparse - 命令行选项与参数解析(转)
- zoj1537- Playing with a Calculator
- XtraBackup应用说明(支持TokuDB)
- PS抠图简单粗暴2种方法
- Telegraf安装与介绍
- 扒一扒开源世界有哪些licenses?
- go中的读写锁RWMutex
- 【Luogu4723】线性递推(常系数齐次线性递推)
- Codeforces 1072 C - Cram Time
- 《算法》第四章部分程序 part 11
- 数组转xml格式/xml格式转数组
- _编程语言_C++_宏定义#define 和 常量const 的区别
- HTML5 manifest离线缓存技术
热门文章
- VC++深入详解读书笔记-第六章菜单
- WinForm(C#)自定义控件之——RoundButton(圆形按钮)
- django 自定用户系统 以及 Django Model 定义语法
- mybatis常用语句
- web标准(复习)--2 列布局
- Python学习笔记总结(四)异常处理
- 用js实现两个select下拉框之间的元素互相移动
- iOS 第三方 需要 引用的库
- Microsoft.Practices.Unity 给不同的对象注入不同的Logger
- Oracle 提示密码过期问题:the password will expire