洛谷 P7054 [NWRRC2015]Graph 题解

一、题目：

洛谷原题

codeforces原题

二、思路：

一道史诗级的思维题。

首先我们来考虑，如果没有加边操作，怎么才能求出来字典序最小的拓扑序，无非就是将普通拓扑排序中的队列换成小根堆。

再来考虑加边操作。对于当前小根堆中保存的入度为 0 的点，我们肯定想加一些指向它们的边从而不让它们出现在这一位；反过来，我们又想在这一位放入尽可能大的点。所以可以有以下算法：

维护一个大根堆 (q) 和一个小根堆 (p)。(p) 维护的是当前所有入度为 0 的点，(q) 中维护的是已经确定要连一条指向它们的边的那些点。设 (a) 为最优拓扑序的上一位，(b) 为最优拓扑序的当前位（等待被求解）。

尝试将 (p) 中的元素加入到 (q) 中。如果 (p) 中只有一个元素且该元素还比 (q) 的堆顶大，那么就可以不用浪费一次加边的机会，直接将该点确定为 (b)。否则的话，依次将 (p) 中的元素插入到 (q) 并让 (kgets k-1)，直到 (p) 变空或者 (k) 变成 (0)。

操作完一轮后，如果 (p) 中还有元素，说明我们不得不将 (p) 的堆顶作为 (b)。否则就可以将 (q) 的堆顶作为 (b)，并连一条新边 ((a,b))。

最后，令 (b) 的后继的入度自减 1。要是减为 0，就加入到 (p) 中。

三、代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
#define FILEIN(s) freopen(s, "r", stdin)
#define FILEOUT(s) freopen(s, "w", stdout)
#define mem(s, v) memset(s, v, sizeof s)

inline int read(void) {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return f * x;
}

const int MAXN = 100005;

int n, m, K;
int in[MAXN], ans[MAXN];

vector<int>linker[MAXN];
vector<pair<int, int> >add;

priority_queue<int, vector<int>, greater<int> >p;
priority_queue<int>q;

int main() {
    FILEIN("graph.in"); FILEOUT("graph.out");
    n = read(); m = read(); K = read();
    for (int i = 1; i <= m; ++ i) {
        int x = read(), y = read();
        linker[x].push_back(y);
        ++ in[y];
    }
    for (int i = 1; i <= n; ++ i) {
        if (!in[i]) p.push(i);
    }
    int a, b;
    for (int i = 1; i <= n; ++ i) {
        while (!p.empty() && K > 0) {
            int y = -1, x = p.top();
            if (q.size()) y = q.top();
            if (x > y && p.size() == 1) break;
            p.pop(); q.push(x); -- K;
        }
        if (!p.empty()) {
            b = p.top(); p.pop();
        }
        else {
            b = q.top(); q.pop();
            add.push_back({ a, b });
        }
        ans[i] = b;
        for (auto &y : linker[b]) {
            -- in[y];
            if (!in[y]) p.push(y);
        }
        a = b;
    }
    for (int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
    puts("");
    printf("%d
", (int)add.size());
    for (auto &p : add)
        printf("%d %d
", p.first, p.second);
    return 0;
}