bzoj 1517 [POI2006]Met 贪心

[POI2006]Met

Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 203 Solved: 108
[Submit][Status][Discuss]

Description

给出一棵N个结点的树，选择L条路径，覆盖这些路径上的结点，使得被覆盖到的结点数最多。

Input

第一行两个正整数N、L(2 <= N <= 1,000,000, 0 <= L <= N)。下面有N-1行，每行两个正整数A和B(1 <= A, B <= N)，表示一条边(A,B)。

Output

一个整数，表示最多能覆盖到多少结点。

Sample Input

17 3
1 2
3 2
2 4
5 2
5 6
5 8
7 8
9 8
5 10
10 13
13 14
10 12
12 11
15 17
15 16
15 10

Sample Output

HINT

鸣谢Oimaster

Source

选择路径的代价相同显然考虑贪心。
首先我们可以按照拓扑关系把原图分层。
接下来我们考虑，对于每一层来说，我们显然最多选取2*l个点。
我们最终选的路径一定是l对叶子节点到另一个叶子节点异或是都选。
又每一个叶子节点一定由上一层的来，所以选叶子节点的话一定会覆盖其他层的点。
=-=噫
我知道我说的好乱。
结论是什么呢？
对于每一层来说，对答案的贡献是min(2*l,num[dep])
num[dep]代表第dep层的节点个数。
求和即可。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define N 1000100

 using namespace std;

 int head[N],cnt;

 int n,l;

 int in[N];

 int dep[N];

 int sum[N];

 struct node

 {

     int from,to,next;

 }edge[N<<];

 void init()

 {

     memset(head,-,sizeof(head));

     cnt=;

 }

 void edgeadd(int from,int to)

 {

     edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];

     head[from]=cnt++;

 }

 void topsort()

 {

     queue<int>q;

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

     {

         if(in[i]==)

             dep[i]=,q.push(i),sum[]++;

     }

     while(!q.empty())

     {

         int u=q.front();

         q.pop();

         for(int i=head[u];i!=-;i=edge[i].next)

         {

             int to=edge[i].to;

             in[to]--;

             if(in[to]==)

             {

                 dep[to]=dep[u]+;

                 sum[dep[to]]++;

                 q.push(to);

             }

         }

     }

     int ans=;

     for(int i=;sum[i];i++)

     {

         ans+=min(sum[i],*l);

     }

     printf("%d\n",ans);

 }

 int main()

 {

     init();

     scanf("%d%d",&n,&l);

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

     {

         int x,y;

         scanf("%d%d",&x,&y);

         edgeadd(x,y);

         edgeadd(y,x);

         in[x]++,in[y]++;

     }

     topsort();

 }

巴特西