题解：AT_abc304_h [ABC304Ex] Constrained Topological Sort

· · 题解

蒟蒻今天刷老师给的图论题单的时候意外自己切了一道紫题，于是来写题解。

我们先观察一下两个限制。
限制一，对于所有 i=1,2,\ldots,M，都有 P_{s_i} < P_{t_i}。因为 s_i,t_i 分别代表第 i 条边起点下表与终点下标，代表的都是点的下标。所以我们可以考虑用点的下标对应排列的下标完成点与排列中的数的一一对应。那么限制就变成若 u 连向 v，则在排列中对应的数字 P_u 必然小于 P_v 这个限制与我们在有向无环图中的拓扑序是一样的，我们发现二者在本题中是等价的。
所以限制一就是在告诉我们 P 是该图的某个拓扑序（P_i 代表 i 号点在拓扑排序中出队的时间）。

限制二，对于所有 i=1,2,\ldots,N，都有 L_i \leq P_i \leq R_i。因为我们看到这个限制我们有一个最直接的贪心想法：对于队列中当前所有 L 满足的点中选取 R 最小的点出队。但是我们发现这个想法是错误的，因为有可能存在某个点 R 很大，但是它连向的某个点 R 很小。所以为了体现该点后面点对选取的影响，我们可以先进行一次反向拓扑，将后续的每个 R 都与当前 R 取 \min。因为我们每次选取 R 最小的点，所以若按某种选取若无法满足，则无论如何调换选取顺序都无法满足。

code

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, m, cnt, l[N], r[N], ind1[N], ind2[N], ans[N];
vector<int> g2[N], g1[N];
struct node{ int x, y; };
inline bool operator <(const node &x, const node &y) { return x.y ^ y.y ? x.y > y.y : x.x > y.x; }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = m; i; --i) {
        int s, t;
        cin >> s >> t;
        g1[s].push_back(t), g2[t].push_back(s);
        ++ind1[t], ++ind2[s];
    }
    for(int i = 1; i <= n; ++i) 
        cin >> l[i] >> r[i];
    queue<int> q;
    for(int i = n; i; --i) 
        if(!ind2[i]) q.push(i);
    while(!q.empty()) {
        ++cnt;
        int aa = q.front();
        q.pop();
        for(int i = g2[aa].size() - 1; ~i; --i) {
            int to = g2[aa][i];
            --ind2[to], r[to] = min(r[to], r[aa]);
            if(!ind2[to]) q.push(to);
        }
    }
    if(cnt < n) {
        puts("No");
        return 0;
    }
    priority_queue<node> q1, q2;
    for(int i = n; i; --i) 
        if(!ind1[i]) q2.push({i, l[i]});
    int now = 1;
    while(!q1.empty() || !q2.empty()) {
        while(!q2.empty()) {
            node aa = q2.top();
            if(aa.y <= now) {
                q2.pop();
                q1.push({aa.x, r[aa.x]});
            } else break;
        }
        if(!q1.empty()) {
        node aa = q1.top();
        q1.pop();
        if(r[aa.x] < now) {
            cnt = 0;
            break;
        }
        ans[aa.x] = now;
        //cout << aa.x << "  " << now << endl;
        for(int i = g1[aa.x].size() - 1; ~i; --i) {
            int to = g1[aa.x][i];
            --ind1[to];
            if(!ind1[to]) q2.push({to, l[to]});
        }
        }
        ++now;
    }
    if(cnt) {
        puts("Yes");
        for(int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    } else puts("No");
    return 0;
}