[ CodeVS冲杯之路 ] P1091

　　不充钱，你怎么AC？

　　题目：http://codevs.cn/problem/1091/

　　大家都写的 DFS，然而我想到了一种贪心的做法，重点是可以A

　　普遍的贪心是每次删掉该深度子树最大的点，但是如果有一边卡一条链就会WA

　　我们何不进一步考虑贪心，如果它下面是一条链我们就可以缓一缓到第 2 天再删是不是，反正它每次也就增加一个人

　　用 size[x] 记录所有后代加上自己的节点个数，f[x] 记录其最大子树的 size 值

　　我们考虑第一次不删这个节点，让它先扩展一次，然后第二次再删除它子树中 size 最大的节点

　　那么设 g[x]=size[x]-f[x]，g 就为第一次不删，第二次删掉其最大的子树还剩余的节点数

　　一条链的 g[x]=1，而一个多叉节点的 g[x]>1，这就意味着先要删去 g 值更大的那个节点，才能不让它下一次扩展更多的出来

　　那么一层层地贪心，每次删掉 g 值最大的节点，直到不再继续传染为止

　　贪心跑得飞快~

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<stack>

 using namespace std;

 const int N=;

 stack<int> s,q;

 int first[N],v[N*],next[N*],size[N],g[N],f[N];

 void dfs(int x,int fa)

 {

     f[x]=fa;

     int i;

     for (i=first[x];i;i=next[i])

         {

             if (v[i]==fa) continue;

             dfs(v[i],x);

             if (size[v[i]]>g[x]) g[x]=size[v[i]];

         }

     size[fa]+=size[x];

 }

 int main()

 {

     int n,m,i,x,ans=;

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

     for (i=;i<=m;i++)

         {

             scanf("%d%d",&x,&v[i]);

             v[i+m]=x;

             next[i]=first[x];

             first[x]=i;

             next[i+m]=first[v[i]];

             first[v[i]]=i+m;

         }

     for (i=;i<=n;i++) size[i]=;

     dfs(,);

     for (i=;i<=n;i++) g[i]=size[i]-g[i];

     s.push();

     g[]=size[]=;

     ans=n;

     while (!s.empty())

         {

             m=;

             while (!s.empty())

                 {

                     x=s.top();

                     s.pop();

                     for (i=first[x];i;i=next[i])

                         {

                             if (v[i]==f[x]) continue;

                             if (g[v[i]]>g[m]||(g[v[i]]==g[m]&&size[v[i]]>size[m])) m=v[i];

                             q.push(v[i]);

                         }

                 }

             while (!q.empty())

                 {

                     x=q.top();

                     q.pop();

                     if (x==m) ans-=size[m];

                     else s.push(x);

                 }

         }

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

     return ;

 }

　　这里有个DFS的：http://blog.csdn.net/yuyanggo/article/details/48087431

　　贪心的做法证明有人会严谨的吗？会的话告诉我谢谢！

巴特西

[ CodeVS冲杯之路 ] P1091

最新文章

热门文章