自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:08:48，当前版本为作者最后更新于2025-01-30 23:26:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

赛时把这道题想复杂了。。。

设函数 $\text{solve}(S)$ 表示，考虑所有两个点都在 $S$ 中的限制，构造出一棵合法的树。

显然，我们要确定根。显然它会成为 $S$ 中所有节点的祖先，如果它被限制有一个祖先或者被限制不能是其他人的祖先，就倒闭了。如果我们确定根，把祖孙关系弱连通的点划分为同一个集合，继续做。

这样的点可能有很多，是不是随便选一个就行了呢？也就是很容易让人担心，每一步随便选是否有影响。

我们建立一张图，只保存限制 $1$。最后一步肯定存在一个 $S$，使得其导出子图所有入度为 $0$ 的点，都会被限制 $2$ 干趴下。

发现 $S$ 中任何一个节点都不可能被选做根。那么 $S$ 就永远不会被分为两个集合。所以如果出现了无解的情况，不必自责你选错点了——因为无论如何都是无解。

暴力做就行了，复杂度 $O(nm)$。

写的比较丑陋，多了个 $\log$，但是速度还行。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1000+10;
int n,m,fa[MAXN],flg[MAXN],res[MAXN];
struct Edge {int x,y,tp;};
int find(int k) {return (fa[k]==k)?k:(fa[k]=find(fa[k]));}
void merge(int u,int v) {return fa[find(v)]=find(u),void();}
int solve(vector<int> S,vector<Edge> lim) {
	if(S.size()==1) return S[0];
	for(auto id:S) fa[id]=id,flg[id]=0;
	for(auto e:lim) if(e.tp==0) flg[e.x]=1; else flg[e.y]=1;
	int rt=0;
	for(auto id:S) if(!flg[id]) rt=id;
	if(!rt) {cout<<"NIE";exit(0);}
	for(auto e:lim) if(e.tp==0&&e.x!=rt&&e.y!=rt) merge(e.x,e.y);
	map<int,vector<int>> mp;
	map<int,vector<Edge>> ed;
	for(auto id:S) if(id!=rt) mp[find(id)].push_back(id);
	for(auto e:lim) if(find(e.x)==find(e.y)) ed[find(e.x)].push_back(e);
	for(auto pr:mp) {
		auto ss=pr.second;
		int id=pr.first;	
		res[solve(ss,ed[id])]=rt;
	}
	return rt;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	vector<Edge> lim;
	ffor(i,1,m) {
		int x,y;
		char c;
		cin>>x>>y>>c;
		lim.push_back({x,y,c=='N'});	
	}
	vector<int> al;
	ffor(i,1,n) al.push_back(i);
	int rt=solve(al,lim);
	ffor(i,1,n) cout<<res[i]<<'\n';
	return 0;
}