Chlience

【题解】LOJ 2114 「HNOI2015」菜肴制作
Problem给定 $n$ 个编号为 $1-n$ 的点,其中有 $m$ 条先后限制关系要求给出选点顺序,使 $1$...
扫描右侧二维码阅读全文
11
2019/02

【题解】LOJ 2114 「HNOI2015」菜肴制作

Problem

给定 $n$ 个编号为 $1-n$ 的点,其中有 $m$ 条先后限制关系

要求给出选点顺序,使 $1$ 号点尽量早的选出,在满足 $1$ 号点的情况下使 $2$ 号点尽量早的选出,在满足 $1,2$ 号点的情况下使 $3$ 号点尽量早的选出 $\cdots$

Thought

要求:拓扑序编号小的尽量靠前

注意:不是字典序最小!

考虑当前有两个可选点 $i,j$ ,其中 $i<j$
不一定先选 $i$ 再选 $j$ ,因为 $j$ 可能是一个比 $i$ 更小的点的前提条件
所以说字典序最小是错的...

正确做法是反序字典序最大

证明咕咕咕了

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100010
struct edge {
    int to;
    int next;
} e[N];
int head[N], tot;
int heap[N], total;
int in[N];
int a[N];
int n, m;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while ((ch > '9' || ch < '0') && ch != '-') ch = getchar();
    if (ch == '-')
        flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
    return ans * flag;
}
void addedge(int a, int b) {
    e[++tot].to = b;
    e[tot].next = head[a];
    head[a] = tot;
};
void push(int x) {
    heap[++total] = x;
    int temp = total;
    while (heap[temp] > heap[temp / 2] && temp != 1) {
        swap(heap[temp], heap[temp / 2]);
        temp /= 2;
    }
    return;
}
void pop() {
    heap[1] = 0;
    heap[1] = heap[total];
    heap[total--] = 0;
    int son, temp = 1;
    while ((temp << 1) <= total) {
        son = (temp << 1);
        if (son + 1 <= total && heap[son + 1] > heap[son])
            ++son;
        if (heap[temp] < heap[son])
            swap(heap[temp], heap[son]);
        temp = son;
    }
    return;
}
void work() {
    memset(in, 0, sizeof(in));
    memset(head, 0, sizeof(head));
    tot = total = 0;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        int a = read(), b = read();
        addedge(b, a);
        ++in[a];
    }
    for (int i = 1; i <= n; i++)
        if (!in[i])
            push(i);
    for (int i = 1; i <= n; i++) {
        if (total) {
            a[n - i + 1] = heap[1];
            pop();
            for (int j = head[a[n - i + 1]]; j; j = e[j].next) {
                --in[e[j].to];
                if (!in[e[j].to])
                    push(e[j].to);
            }
        } else {
            puts("Impossible!");
            return;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts("");
}
int main() {
    int t = read(
    while (t--) {
        work();
    return 0;
}
Last modification:February 11th, 2019 at 10:24 am

Leave a Comment