51nod 1273 旅行计划—

某个国家有N个城市，编号0 至 N-1，他们之间用N - 1条道路连接，道路是双向行驶的，沿着道路你可以到达任何一个城市。你有一个旅行计划，这个计划是从编号K的城市出发，每天到达一个你没有去过的城市，并且旅途中经过的没有去过的城市尽可能的多（如果有2条路线，经过的没有去过的城市同样多，优先考虑编号最小的城市），直到所有城市都观光过一遍。现在给出城市之间的交通图T，以及出发地点K，你来设计一个旅行计划，满足上面的条件。例如：

(K = 2)

第1天从2到0 (城市 1 和 0 变成去过的)

第2天从0到6 (城市 4 和 6 变成去过的)

第3天从6到3 (城市 3 变成去过的)

第4天从3到5 (城市 5 变成去过的)

上图的输入数据为：0 1 2 2 1 4。共7个节点，除节点0之外，共6行数据。

第1个数0表示1到0有1条道路。

第2个数1表示2到1有1条道路。

Input

第1行：2个数N，K(1 <= N <= 50000, 0 <= K <= N - 1)

第2 - N + 1行：每行一个数，表示节点之间的道路。

Output

输出旅行的路线图，即每天到达的城市编号。

Input示例

Output示例

2

0

6

3

5
————————————————————————————————————————————————————
以下搬自51nod题解
考虑将树根设为K，观察到以下结论：
1. 每次必然会走到叶子，否则可以继续向下走到叶子，使得访问的点增多。
2. 考虑每次访问到的未访问的点，一定是与叶子相连的、在叶子到点K路径上的一条连续的链，
所以问题可以转化为：
令每个叶子分别支配一条链，使得标号小的点尽量支配多的点，最后根据支配的点数多少、标号大小依次访问。
以做法可以是树上贪心，从深到浅依次确定每个点被其子树里哪个叶子支配，
然后使得那个点的支配点个数加一，
最后用基数排序排出支配点数降序、标号大小升序即可。
当然我懒 所以写的是sort代替基排

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

char s[];int len;

inline void outx(int x)

{

    if(!x){putchar('');return;}

    while(x)s[++len]=x%,x/=;

    while(len)putchar(s[len--]+);

}

int T,n,rt;

int first[M],cnt;

struct node{int to,next;}e[M*];

void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}

void insert(int a,int b){ins(a,b); ins(b,a);}

int sum;

struct pos{int d,pos;}p[M];

bool cmp(pos a,pos b){return a.d!=b.d?a.d>b.d:a.pos<b.pos;}

void dfs(int x,int fa,int deep){

    bool f=true;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now!=fa) f=false,dfs(now,x,deep+);

    }

    if(f&&x!=rt) p[++sum].pos=x,p[sum].d=deep;

}

int vis[M];

struct Ans{int h,pos;}q[M];

bool qcmp(Ans a,Ans b){return a.h!=b.h?a.h>b.h:a.pos<b.pos;}

int find(int x,int fa){

    if(vis[x]||x==rt) return ;

    for(int i=first[x];i;i=e[i].next){

        int now=e[i].to;

        if(now==fa) continue;

        if(find(now,x)) return T++,vis[x]=,;

    }

    return ;

}

int main()

{

    int x;

    n=read(); rt=read();

    for(int i=;i<n;i++) x=read(),insert(i,x);

    for(int i=;i<=n;i++) p[i].pos=i;

    dfs(rt,-,); sort(p+,p++sum,cmp);

    for(int i=;i<=sum;i++){

        q[i].pos=p[i].pos;

        T=; find(p[i].pos,-);

        q[i].h=T;

    }

    sort(q+,q++sum,qcmp);

    printf("%d\n",rt); for(int i=;i<=sum;i++) printf("%d\n",q[i].pos);

    return ;

}

巴特西

51nod 1273 旅行计划——思维题

最新文章

热门文章