【P2325】王室联邦(树的遍历+贪心)

在肖明

#神#
的推荐下，我尝试了这个题，一开始想的是暴力枚举所有的点，然后bfs层数，试着和肖明

#神#
说了这种方法之后，

#神#
轻蔑的一笑，说这不就是一个贪心么，你只需要先建树，然后从底下向上遍历，够了B个点就算作一个省。

#神#
的话让我豁然开朗，这个题貌似真的不是那么难诶。

然后
#神#
回去写作业了，蒟蒻我还在机房里思考

#神#
的话。仔细想了一下，发现这么贪心正确性显然。像

#神#
说的遍历树，然后当整棵树基本上快遍历完的时候，会出现剩下几个点不够B个的情况，然后就直接把他们连到根上，可以知道，因为我们之前是每个省都是B个城市，所以就算加到根上，根的那个省的城市还是会小于3\*B，所以这么就可以得出最优解。

然而书上的代码蒟蒻实现难度太高，，所以又借助了一下题解的力量。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#define re register

#define maxn 1000007

#define ll long long

using namespace std;

struct po

{

    int to,from,nxt;

};

po edge[];

int head[],n,m,B,b[],ans,t,rt[],fa,cnt,srk[],num,s;

inline void add_edge(int from,int to)

{

    edge[++num].nxt=head[from];

    edge[num].to=to;

    head[from]=num;

}

inline void dfs(int u,int f)

{

    int q=fa;

    for(re int i=head[u];i;i=edge[i].nxt)

    {

        if(edge[i].to==f)

        continue;

        dfs(edge[i].to,u);

        if(fa-q>=B)

        {

            cnt++;

            rt[cnt]=u;

            while(fa>q)

            {

                b[srk[fa--]]=cnt;

            }

        }

    }

    srk[++fa]=u;

}

int main()

{

    cin>>n>>B;

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

    {

        cin>>s>>t;

        add_edge(s,t);

        add_edge(t,s);

    }

    dfs(,);

    while(fa)

    {

        b[srk[fa--]]=cnt;

    }

    cout<<cnt<<endl;

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

    cout<<b[i]<<" ";

    cout<<endl;

    for(re int i=;i<=cnt;i++)

    {

        cout<<rt[i]<<" ";

    }

    return ;

}

巴特西

【P2325】王室联邦(树的遍历+贪心)

最新文章

热门文章