Luogu P3243 [HNOI2015]菜肴制作

题目描述

https://www.luogu.com.cn/problem/P3243

简要题意：给定一个 $n$ 个点 $m$ 条边的有向无环图，求一个特殊的拓扑序，满足 $1$ 出现的位置尽量靠前，在满足这个条件的情况下，$2$ 出现的位置尽量靠前，然后是 $3$，依次类推

$n,m\le 10^5$

Solution

我们考虑原图中 $1$ 尽早出现等价于反图中 $1$ 最晚出现

所以我们考虑将图反向，然后我们一直进行拓扑排序的操作直到将除了 $1$ 以外的其它能弹出的点都弹出

这是 $1$ 的最晚出现位置，也是原图中 $1$ 的最早出现位置

我们对于之前出队的元素和现在在队中元素分别进行对应操作

能够发现我们每次让反图中最大的元素出队可以完成上述操作

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 100010
#define maxm 100010
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxm * 2]; int c1, head[maxn], in[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

priority_queue<int> Q; vector<int> ans;
void topsort() {
    for (int i = 1; i <= n; ++i)
        if (!in[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.top(); Q.pop(); ans.push_back(u);
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (--in[v] == 0) Q.push(v);
        }
    }
}

void init() {
    fill(head, head + maxn, -1);
    fill(in, in + maxn, 0);
    c1 = 0; ans.clear();
}

void work() {
    cin >> n >> m; init();
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(y, x); ++in[x];
    } topsort();
    if (ans.size() < n) return (void) (cout << "Impossible!\n");
    reverse(ans.begin(), ans.end());
    for (auto u : ans) cout << u << " "; cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}