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

· · 题解

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;
}