题解：P10521 [XJTUPC2024] 瑟莉姆的宴会

ldll0721 · 2024-05-21 20:31:27 · 题解

首先这个题我们需要的是最后总值为正，也就是说需要让更多人满足条件中 (x,y) 。

所以我们就可以用一个 f(x,y) 来表示支配者与被支配者，然后选出一个能支配别人人数最多的一个作为根，最后 dfs 一遍寻找位置就可以了（满足条件就放进去）。如果遇到不包含在内（即无法增加影的值），则统一将他的支配者归为主根。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,t[500005],fa[500005],vis[500005],ans[500005];
void dfs(int u){
    vis[u]=1;
    for(int i=1;i<=n;i++){
        if(vis[i]==0&&fa[i]==u){
            ans[i]=u;
            dfs(i);
        }
    }
}
signed main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        t[x]++;//t[i]用来保存每一位的可支配者数量 
        fa[y]=x;//表示y可以被x支配 
    }
    int maxn=0,bh;
    for(int i=1;i<=n;i++){
        if(t[i]>maxn){
            maxn=t[i];
            bh=i;
        }
    }
    dfs(bh);//bh为最大值，即主根 
    for(int i=1;i<=n;i++){
        if(ans[i]==0&&i!=bh)ans[i]=bh;//遇到未放入则归为主根 
        cout<<ans[i]<<" ";
    }
    return 0;
}