题解：P14624 [2018 KAIST RUN Fall] Dumae

· · 题解

P14624 [2018 KAIST RUN Fall] Dumae 题解

题目传送门

题意描述

有 n 个人，第 a_i 个人有一个排列的限制区间 [L_i,R_i]，同时给出 m 组 \{u_i,v_i\}，表示第 u_i 个人排在第 v_i 个人的前面。
若存在合法的方案，则给出任意一种；若不存在，输出 -1。

思路

一道拓扑+贪心题。我们先进行拓扑排序（无解输出 -1 并结束），由于其给出了限制区间，我们还需要检验拓排的正确性。贪心处理：若第 i 个人的排位为 to_i，那么遍历排位在 i 之后的每个 j，转移状态：L_j=\max\{L_j,L_i+1\} 同理，遍历排位在 i 之后的每个 j，转移状态：R_i=\min\{R_i,R_j-1\}。经过这么处理，我们拓排的每个链区间就两两不相交了，接下来检验每个 L_i 是否小于等于 R_i，以及每个 R_i 是否大于等于在序列中的排位 ans_k 即可，最终输出答案序列 ans。

::::info[code]{open}

#include <bits/stdc++.h>
#define pairr pair<int,int>
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    for(;ch>57||ch<48;ch=getchar())if(ch=='-')f=-1;
    for(;ch>47&&ch<58;ch=getchar())res=(res<<3)+(res<<1)+(ch^48);
    return res*f;
}
inline int Min(int a,int v){return a<v?a:v;}
inline int Max(int a,int v){return a>v?a:v;}
int n,m,f,cnt,p;
int l[300005],r[300005],to[300005],in[300005];
vector<int>g[300005],ans;
vector<pairr>a[300005];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        l[i]=read(),r[i]=read();
    }
    for(int i=1;i<=m;i++){
        int u=read(),v=read();
        g[u].push_back(v);
        in[v]++;
    }
    queue<int>q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i),cnt++;
    while(!q.empty()){
        int u=q.front();
        to[++p]=u;
        q.pop();
        for(int i=0;i<g[u].size();i++){
            in[g[u][i]]--;
            if(!in[g[u][i]])q.push(g[u][i]),cnt++;
        }
    }
    if(cnt!=n){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        int u=to[i];
        for(int j=0;j<g[u].size();j++){
            int v=g[u][j];
            l[v]=Max(l[v],l[u]+1);
        }
    }
    reverse(to+1,to+1+n);
    for(int i=1;i<=n;i++){
        int u=to[i];
        for(int j=0;j<g[u].size();j++){
            int v=g[u][j];
            r[u]=Min(r[u],r[v]-1);
        }
    }
    for(int i=1;i<=n;i++){
        if(l[i]>r[i]){
            cout<<-1;
            return 0;
        }
    }
    priority_queue<pairr,vector<pairr>,greater<pairr> >rq;
    for(int i=1;i<=n;i++)a[l[i]].push_back(pairr(r[i],i));
    for(int i=1;i<=n;i++){
        for(int j=0;j<a[i].size();j++)rq.push(a[i][j]);
        if(rq.empty()){
            cout<<-1;
            return 0;
        }
        if(rq.top().first<i){
            cout<<-1;
            return 0;
        }
        int u=rq.top().second;
        rq.pop();
        ans.push_back(u);
    }
    for(int i=0;i<n;i++)cout<<ans[i]<<'\n';
    return 0;
}

::::