自动搬运

查看原文

来自洛谷，原作者为

	x义x “我们要走多远？”“一百万年。”

搬运于2025-08-24 22:26:14，当前版本为作者最后更新于2021-08-27 09:33:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意.

给定一张 $n$ 点 $m$ 条边的 DAG，你可以至多添加 $k$ 条有向边，使得这仍然是一个 DAG，使得字典序最小的拓扑序的字典序尽量大。

输出这个拓扑序以及方案。

$n,m,k\le 10^5$。

啊又是开门一个 key obeservation 的题。

引理.

若最终拓扑序为 $p$，那么存在一种最优方案满足所有加的边都形如 $p_i\Rightarrow p_{i+1}$。

证明.

否则，我们总是可以把 $p_{i}\Rightarrow p_j$ 替换为 $p_{i+1}\Rightarrow p_j$。说明如下。

设替换后的新排列为 $q$。

• 显然 $p_1=q_1,...,p_i=q_i$。这部分的拓扑排序完全和这条边没关系。
• 又可以发现 $q_{i+1}\neq p_j$，因为此时仍存在 $p_{i+1}\Rightarrow p_j$。其他点的情况和该边换不换没关系，所以 $q_{i+1}=p_{i+1}$。
• 如果再往后，那所有点的情况都和该边换不换没关系。

现在我们逐位确定 $p$。如果 $k=0$，那自然是没戏唱了，直接开始拓扑排序即可。

否则，

现在将所有入度为 $0$ 的节点取出，考虑其中的最小者 $u$：

• 如果 $u$ 并非唯一的入度为 $0$ 元素，那我们肯定不希望 $u$ 当上当前位置，所以我们希望临时加一条边把 $u$ 放到后面去（让它的度数不为 $0$）。
• • $k\leftarrow k-1$；显然这条边连肯定是能连的（$u$ 并非唯一的入度为 $0$ 元素）；至于这条边到底和谁连，我们暂时不关心。到时候只需要在求出 $p$ 之后根据上面的引理编出所需的边即可。
• 如果 $u$ 就是唯一的入度为 $0$ 元素，那么只好把 $u$ 作为当前位置，删去 $u$。

听起来十分美好，但这个过程是明显有问题的。这个问题体现在最后【删去 $u$】处：我们没有考虑 $u$ 可能连出了一些新加边，自然也就没有更新目标节点的度，它们就永远入度为 $1$ 了！

所以我们应当维护两个集合：

• 所有【明显是入度为 $0$】的节点；
• 和所有【因为被一条新加边连入而可能现在是入度为 $0$】的节点。

顺便，我们指出，对于这些【可能是入度为 $0$】的节点，我们在任何时刻钦定它入度为 $0$ 都是合法的：显然只要我们不认为它入度为 $0$，它的后继节点们就不可能被处理，从而不会连出环。

下面是修正后的流程。

现在将所有入度为 $0$ 的节点取出，考虑其中的最小者 $u$：

• 如果 $u$ 并非唯一的入度为 $0$ 元素，那我们肯定不希望 $u$ 当上当前位置，所以我们希望临时加一条边把 $u$ 放到后面去（让它的度数不为 $0$）。
• • $k\leftarrow k-1$；显然这条边连肯定是能连的（$u$ 并非唯一的入度为 $0$ 元素）；至于这条边到底和谁连，我们暂时不关心。到时候只需要在求出 $p$ 之后根据上面的引理编出所需的边即可。
• 如果 $u$ 就是唯一的入度为 $0$ 元素：
• • 那么我们应当把【可能是入度为 $0$】的节点中的最大者取出替换掉 $u$。（当然，如果它比 $u$ 小那还不如不换，还是把认定 $u$ 就是当前位置并删除吧）

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100005;

int n, K, k;
vector<int> G[maxn];
int deg[maxn];

priority_queue<int, vector<int>, greater<int> > U;
priority_queue<int> V;

void del(int u) {
    for (int v : G[u])
        if (!(--deg[v])) U.push(v);
}
int p[maxn], tot;
bool qaq[maxn];

int main() {
    int m;
    scanf("%d%d%d", &n, &m, &K);
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v);
        deg[v]++;
    }
    for (int i = 1; i <= n; i++) if (deg[i] == 0) U.push(i);
    while (tot != n) {
        if (U.empty()) {
            int u = V.top(); V.pop();
            del(u); p[++tot] = u; continue;
        }
        int u = U.top(); U.pop();
        if (k == K) { del(u); p[++tot] = u; continue; }
        if (!U.empty()) {
            k++;
            qaq[u] = 1;
            V.push(u);
            continue;
        }
        if (V.empty()) { del(u); p[++tot] = u; continue; }
        int v = V.top();
        if (v < u) { del(u); p[++tot] = u; continue; }
        V.pop(), V.push(u), U.push(v), qaq[u] = 1, k++;
    }
    for (int i = 1; i <= n; i++) printf("%d ", p[i]); printf("\n");
    printf("%d\n", k);
    for (int i = 2; i <= n; i++) if (qaq[p[i]]) printf("%d %d\n", p[i - 1], p[i]);
}