例题：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
什么意思呢？先声明一件事
对于这种情况
我们这种算法的方案是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吗
评论