注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

树的路径覆盖  

2013-03-30 14:51:49|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
例题:bzoj 1907
PS:非vip用户不能做

用若干条链将树给覆盖,要求条数最少
我膜拜到了一个贪心的算法
cnt[i]表示在i的儿子的子树中的链的个数
结论:
if(cnt[p]==0)  cnt[father[p]]++;
else if(cnt[p]==1)  ans--,cnt[father[p]]++;
else ans-=2;

ans的初值为n

什么意思呢?先声明一件事
对于这种情况
树的路径覆盖 - ydc - ydc的博客
 我们这种算法的方案是2,3,4一组,1一组。于是我们可以定义1是类叶节点
当且仅当一个点是叶节点或类叶节点时cnt[p]=0,可以看作是一条链,cnt[father[p]]++。当一个点的cnt是1时,可以看作是一条链,cnt[father[p]]++,而这个时候显然p要和p的儿子接在一起,所以ans--
当一个点有多于1个儿子的子树是链时,显然是拿某两个子树与他接在一起,这个时候ans-=2.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define Rep(i,l,r) for(int i=l;i<=r;i++)
#define MAXN 10010
#define MAXM 20010
using namespace std;
int n,ans;
int to[MAXM],next[MAXM],start[MAXN],tot;
void make(int a,int b){ tot++,to[tot]=b,next[tot]=start[a],start[a]=tot; }
void read()
{
tot=0;
memset(start,0,sizeof(start));
scanf("%d",&n);
int a,b;
Rep(i,2,n)
{
scanf("%d %d",&a,&b);
make(a,b),make(b,a);
}
ans=n;
}
void BFS()
{
static int queue[MAXN],cnt[MAXN],father[MAXN];
memset(father,0,sizeof(father));
memset(cnt,0,sizeof(cnt));
int front=0,rear=1;
father[1]=n+1,queue[rear]=1;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p],q;i;i=next[i])
if(father[q=to[i]]==0)
father[q]=p,queue[++rear]=q;
}
for(int i=n;i>=1;i--)
{
int p=queue[i];
if(cnt[p]==0) cnt[father[p]]++;
else if(cnt[p]==1) ans--,cnt[father[p]]++;
else ans-=2;
}
}
int main()
{
int test;
for(scanf("%d",&test);test;test--)
{
read();
BFS();
printf("%d\n",ans);
}
return 0;
}


妈蛋当年的我是有多弱啊
这种东西不是想怎么树p就怎么树p吗
  评论这张
 
阅读(415)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017