luoguP7054 题解 - 【NWRRC2015】Graph

· · 题解

题意.

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

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

啊又是开门一个 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）。
  • 如果 u 就是唯一的入度为 0 元素，那么只好把 u 作为当前位置，删去 u。

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

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

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

下面是修正后的流程。

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

  • 如果 u 并非唯一的入度为 0 元素，那我们肯定不希望 u 当上当前位置，所以我们希望临时加一条边把 u 放到后面去（让它的度数不为 0）。
  • 如果 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]);
}