列表

详情

NC54637. [CSP2019]树上的数（tree）

描述

已替换官方数据
给定一个大小为 n 的树，它共有 n 个结点与 n − 1 条边，结点从 1 ∼ n 编号。初始时每个结点上都有一个 1 ∼ n 的数字，且每个 1 ∼ n 的数字都只在恰好一个结点上出现。
接下来你需要进行恰好n − 1 次删边操作，每次操作你需要选一条未被删去的边，此时这条边所连接的两个结点上的数字将会交换，然后这条边将被删去。
n − 1 次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字1 ∼ n 所在的结点编号依次排列，就得到一个结点编号的排列 P_i。现在请你求出，在最优操作方案下能得到的字典序最小的 P_i。

如上图，蓝圈中的数字 1 ∼ 5 一开始分别在结点 ② 、① 、③ 、⑤ 、④ 。按照 (1)(4)(3)(2)的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为 ① ③ ④ ② ⑤ ，该排列是所有可能的结果中字典序最小的。

输入描述

本题输 入包含多组测试数据。
第一行一个正整数 T，表示数据组数。
对于每组测试数据：
第一行一个整数 n，表示树的大小。 
第二行 n 个整数，第 i个整数表示数字 i 初始时所在的结点编号。 接下来 n−1 行每行两个整数 x,y，表示一条连接 x 号结点与 y 号结点的边

输出描述

对于每组测试数据，输出一行共 n 个用空格隔开的整数，表示最优操作方案下所 能得到的字典序最小的 P_i

示例1

输入: 

4 
5 
2 1 3 5 4 
1 3 
1 4 
2 4 
4 5 
5 
3 4 2 1 5 
1 2 
2 3 
3 4 
4 5 
5 
1 2 5 3 4 
1 2 
1 3 
1 4 
1 5 
10 
1 2 3 4 5 7 8 9 10 6 
1 2 
1 3 
1 4 
1 5 
5 6 
6 7 
7 8 
8 9 
9 10

输出: 

1 3 4 2 5
1 3 5 2 4
2 3 1 4 5
2 3 4 5 6 1 7 8 9 10

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 1756ms, 内存消耗: 49460K, 提交时间: 2019-11-21 12:30:47 

#include<bits/stdc++.h>
const int N=2005;
struct adjacent{
	int sz,to[N],o[N],pre[N],nxt[N],s[N],g[N];
	inline void add(int x,int zz){to[++sz]=x;o[sz]=zz;}
	int gfa(int x){return g[x]==x?x:g[x]=gfa(g[x]);}
	inline void ini(){
		memset(pre,-1,sz+2<<2);memset(nxt,-1,sz+2<<2);
		for(int i=0;i<=sz+1;++i)g[i]=i,s[i]=1<=i && i<=sz;
	}
	inline bool ck(int x,int y){
		if(nxt[x]==y && pre[y]==x)return 1;
		if(nxt[x]!=-1 || pre[y]!=-1 || gfa(x)==gfa(y))return 0;
		if(gfa(x)==gfa(0) && gfa(y)==gfa(sz+1) && s[gfa(x)]+s[gfa(y)]<sz)return 0;
		return 1;
	}
	inline void link(int x,int y){
		if(nxt[x]==y)return;
		nxt[x]=y;pre[y]=x;
		x=gfa(x);y=gfa(y);g[x]=y;s[y]+=s[x];
	}
}a[N];
int T,n,x,y,i,p[N],pp[N],mn,faa[N],fee[N];
void dfs(int x,int fa,int fe){
	faa[x]=fa;fee[x]=fe;
	for(int i=1;i<=a[x].sz;++i){
		int y=a[x].to[i];
		if(y==fa)continue;
		if(a[x].ck(fe,i)){
			if(a[y].ck(a[x].o[i],a[y].sz+1) && y<mn)mn=y;
			dfs(y,x,a[x].o[i]);
		}
	}
}
int main(){
////	freopen("tree2.in","r",stdin);
	for(scanf("%d",&T);T--;){
		scanf("%d",&n);
		for(i=1;i<=n;++i)a[i].sz=0;
		for(i=1;i<=n;++i)scanf("%d",pp+i);
		for(i=1;i<n;++i)scanf("%d%d",&x,&y),a[x].add(y,a[y].sz+1),a[y].add(x,a[x].sz);
		for(i=1;i<=n;++i)a[i].ini();
		for(i=1;i<=n;++i){
			mn=N,dfs(pp[i],0,0),printf("%d%c",mn,i==n?'\n':' ');
			a[mn].link(fee[mn],a[mn].sz+1);
			for(x=mn;x!=pp[i];x=faa[x])
				a[faa[x]].link(fee[faa[x]],a[x].o[fee[x]]);
		}
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 533ms, 内存消耗: 32212K, 提交时间: 2022-08-03 17:44:34 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,p[2005],pre[2005][2005],nxt[2005][2005],con[2005];
vector<int>G[2005];
bool chk(int l,int m,int r)
{
	if(pre[m][r]==-1||nxt[m][l]==-1||nxt[m][l]==r)return 0;
	if(nxt[m][l]==0&&pre[m][r]==n+1&&con[m]!=2)return 0;
	return 1; 
}
void uni(int l,int m,int r)
{
	nxt[m][pre[m][r]]=nxt[m][l];
	pre[m][nxt[m][l]]=pre[m][r];
	pre[m][r]=nxt[m][l]=-1;con[m]--;
}
int fnd(int x,int p)
{
	int r=n;if(chk(p,x,n+1))r=min(r,x);
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];if(y==p)continue;
		if(chk(p,x,y))r=min(r,fnd(y,x));
	}
    return r;
}
bool del(int x,int t,int p)
{
	if(x==t){uni(p,x,n+1);return 1;}
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];if(y==p)continue;
		if(del(y,t,x)){uni(p,x,y);return 1;}
	}
    return 0;
}
void sol()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)G[i].clear();
	for(int i=1;i<=n;i++)for(int j=0;j<=n+1;j++)pre[i][j]=nxt[i][j]=j;
	for(int i=1;i<=n;i++)scanf("%d",&p[i]);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	for(int i=1;i<=n;i++)con[i]=G[i].size()+2;
	for(int i=1;i<=n;i++){int t=fnd(p[i],0);printf("%d ",t);del(p[i],t,0);}
	puts("");
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)sol();return 0;
}

上一题

© 2024 nowcoder.com