题解：P11606 [PA 2016] 构树 / Reorganizacja

很好的一道构造题。
看到题目让我们构造一棵树，首先就应该考虑怎么选根：

显然根不能为某个点的后代
显然根一定是所有点的祖先

选不到直接 NIE。
接下来考虑如何往下构造，似乎并没有什么新的性质，那就直接推广选根的操作，把其他一坨节点全挂在根下面。考虑确定了根影响了什么，也就是如果某一节点的祖先一定是根，这个关系就没用了。删掉这些关系，重复选根的操作，注意我们有根了所以以后只需要建森林即可：

如果这个节点想成为一棵树的根显然不能为某个节点的后代。
如果这个节点想成为一棵树的根显然不能既为某个节点的祖先又不能为该节点的祖先。注意前者关系可能要递推，所以要用并查集维护。

显然建不出森林了也要 NIE。
代码如下，一些细节见注释：

CPP

#include<bits/stdc++.h>
//#define int long long
#define db double
#define maxn 3000005
#define mod 998244353
#define fir first
#define sec second
#define pr pair<int,int>
#define pb push_back
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')WW=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX%10+'0');
}
struct con
{
	int x,y;char c;
}e[maxn];
int n,m,rt,fa[maxn],pa[maxn],q[maxn];
bool no[maxn];
int find(int f)
{
	return q[f]==f?f:q[f]=find(q[f]);
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),cin>>e[i].c,e[i].c=='T'?no[e[i].x]=1:no[e[i].y]=1;
	for(int i=1;i<=n;i++)if(!no[i])rt=i;//整棵树的根
	if(!rt)puts("NIE"),exit(0);
	for(int i=1;i<=n;i++)pa[i]=rt,fa[i]=-1;//全挂在根下面，注意fa=0是有意义的要初始化为-1
	fa[rt]=0;
	for(int T=1;T<n;T++)
	{
		for(int i=1;i<=n;i++)q[i]=i,no[i]=(fa[i]==-1?0:1);//在剩余节点中建树
		for(int i=1;i<=m;i++)
			if(fa[e[i].y]==-1&&e[i].c=='T')
			{
				no[e[i].x]=1;//不能为后代
				if(fa[e[i].x]==-1)q[find(e[i].x)]=find(e[i].y);//并查集维护祖先关系
			}
		for(int i=1;i<=m;i++)
			if(e[i].c=='N'&&find(e[i].x)==find(e[i].y))no[e[i].y]=1;//y不能既为x祖先又不能为x祖先
		rt=0;
		for(int i=1;i<=n;i++)if(!no[i])rt=i;//找森林中的某棵树的根
		if(!rt)puts("NIE"),exit(0);//找不到了
		fa[rt]=pa[rt];//与挂上的那个节点确认父子关系
		for(int i=1;i<=n;i++)if(find(i)==find(rt))pa[i]=rt;//与这个根有祖先关系就挂在这个根下面
	}
	for(int i=1;i<=n;i++)write(fa[i]),puts("");
	return 0;
}

题解：P11606 [PA 2016] 构树 / Reorganizacja

文章操作

相关推荐

评论

题解：P11606 [PA 2016] 构树 / Reorganizacja