做个卖东西的网站,深圳银行网站建设,事业单位网站模板,钟表商城网站建设方案正题
题目链接:https://www.luogu.com.cn/problem/P5659 题目大意
给出nnn个点的一棵树#xff0c;每个节点上有一个数字#xff0c;你每次可以选择一条边删除然后交换连接的两个点的数字#xff0c;在删完所有数字后设pip_ipi表示数字iii所在节点编号#xff0c;要求使…正题
题目链接:https://www.luogu.com.cn/problem/P5659 题目大意
给出nnn个点的一棵树每个节点上有一个数字你每次可以选择一条边删除然后交换连接的两个点的数字在删完所有数字后设pip_ipi表示数字iii所在节点编号要求使得排列ppp的字典序。
1≤n≤2000,1≤T≤101\leq n\leq 2000,1\leq T\leq 101≤n≤2000,1≤T≤10 解题思路
好阴间的题目
考虑对与一个点xxx的转移肯定是如下图类似的情况并且每个点连接的边的删除顺序是独立的如果不独立证明出现了环树上显然没有环 考虑上图我们发现产生的数字搬运是x→1,1→2,2→3,3→xx\rightarrow 1,1\rightarrow 2,2\rightarrow 3,3\rightarrow xx→1,1→2,2→3,3→x而边的删除顺序是(x,3)→(x,2)→(x,1)(x,3)\rightarrow (x,2)\rightarrow (x,1)(x,3)→(x,2)→(x,1)红色箭头画反了。不难发现的是因为必须删除所有边所以最后肯定是xxx和它周围的节点连接形成一个搬运环。
然后因为字典序最小所以考虑贪心如果快速对于(s,t)(s,t)(s,t)判断sss上的数字能否搬运到ttt上。
先考虑在s→ts\rightarrow ts→t路径上不包括s,ts,ts,t的节点xxx需要满足的条件记上一个节点为fafafa下一个节点为yyy。
如果有数字走y→xy\rightarrow xy→x或者x→fax\rightarrow fax→fa搬运过那么不行如果边x→yx\rightarrow yx→y或者fa→xfa\rightarrow xfa→x正反都搬运过数字那么不行如果此时对于节点xxx的边中加上fa→yfa\rightarrow yfa→y这条边后形成了一个环且不是所有xxx及其周围的数字都在环上的话那么显然不行。如果边(x,fa)(x,fa)(x,fa)已经要求在(x,y)(x,y)(x,y)之后再删除了那么显然不合法也就是红色的箭头形成了环
对于根节点和终止节点则类似只是减少了上面第444个要求因为显然这条边必须是最早/最晚删除的。
然后用类似链表的结构来维护每个节点连出去边的情况来判断后两个条件前两个条件则很好判断。并且如果保证了对于每个节点xxx都满足它上面的数字不会搬回自己所在处就可以保证所有边必须删除了。
然后每次从未确定的最小的数字所在节点出发搜索所有合法的终止节点然后拿最小值再沿路更新即可。
时间复杂度O(Tn2)O(Tn^2)O(Tn2) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N2100;
struct node{int to,next;
}a[N1];
int T,n,tot,ls[N],p[N],d[N],d1[N],d2[N],fa[N];
int from[N],got[N],e[N][N],las[N][N],nxt[N][N];
bool v[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;d[y];return;
}
void dfs(int x,int root){for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa[x])continue;v[y]1;if(x!root){if(e[fa[x]][x]fa[x]||e[x][y]x)v[y]0;//反向搬运过 if(e[fa[x]][x]0||e[x][y]0)v[y]0;//被别的方向走过if(nxt[x][y]from[x]las[x][fa[x]]got[x]d[x]*2d1[x]d2[x]-20)v[y]0;//构成一条偏序链 if(nxt[x][y]fa[x])v[y]0;//构成环 }else{if(e[x][y]x)v[y]0;//反向搬运过 if(e[x][y]0)v[y]0;//被别的方向走过if(from[x]nxt[x][y]from[x]d[x]d1[x]d2[x]-10)v[y]0;//构成一条偏序链 }v[y]v[x];fa[y]x;dfs(y,root);}if(xroot)v[x]0;else{if(from[x])v[x]0;if(got[x]nxt[x][got[x]]fa[x]d[x]d1[x]d2[x]-10)v[x]0;}return;
}
int main()
{scanf(%d,T);while(T--){scanf(%d,n);tot0;memset(d,0,sizeof(d));memset(ls,0,sizeof(ls));memset(d1,0,sizeof(d1));memset(d2,0,sizeof(d2));memset(got,0,sizeof(got));memset(from,0,sizeof(from));for(int i1;in;i)scanf(%d,p[i]);for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);e[x][y]e[y][x]-1;las[x][y]nxt[x][y]y;las[y][x]nxt[y][x]x;}for(int i1;in;i){int xp[i];for(int j1;jn;j)fa[j]0;v[x]1;dfs(x,x);int y0;for(int j1;jn;j)if(v[j]){yj;break;}printf(%d ,y);from[y]fa[y];while(fa[y]!x){if(e[fa[y]][y]-1){e[fa[y]][y]e[y][fa[y]]fa[y];d[y]--;d2[y];d[fa[y]]--;d1[fa[y]];}else{e[fa[y]][y]e[y][fa[y]]0;d1[y]--;d2[fa[y]]--;}int zy;yfa[y];las[y][nxt[y][z]]las[y][fa[y]];nxt[y][las[y][fa[y]]]nxt[y][z];//数字fa-y-z,所以y-fa的连接y-z }if(e[fa[y]][y]-1){e[fa[y]][y]e[y][fa[y]]fa[y];d[y]--;d2[y];d[fa[y]]--;d1[fa[y]];}else{e[fa[y]][y]e[y][fa[y]]0;d1[y]--;d2[fa[y]]--;}got[x]y;}putchar(\n);}return 0;
}
