题解 CF825E【Minimal Labels】

· · 题解

偶然间翻到三个月前写的这个题，发现现有的题解均未给出解法的正确性证明，只是不明不白地写了一些对理解做法毫无帮助的话。我认为解法的正确性并不显然，因此这篇题解主要给出正确性证明，补上逻辑漏洞。

解法与其他题解一样，即：建反图，然后跑拓扑排序，每次优先取出可以取出的编号最大的点，从 n 到 1 赋权值。

这似乎有点反直觉：为什么倒着做就恰好能满足字典序最小呢？相信大多数人的第一反应都是正着做，这也是我认为正确性并不显然的原因。

证明：

以下“入边”“出边”“入度”“出度”等均为原图上的。

考虑整个算法的第一步，也就是分配权值 n。显然，权值 n 的点出度必须为 0。

我们记在上述算法中，被分配了权值 n 的点的编号为 u。利用反证法，假设在另一种分配方案中，u 被分配了权值 x（x < n），而 v 被分配了权值 n。由于算法中取出的 u 是编号最大的出度为 0 的点，而 v 的出度也必须为 0，因此我们有 u > v。

对于这种分配方案中被分配权值 x+1\sim n 的点，我们可以将它们重新分配 x\sim n-1 的权值，并将 u 重新分配 n 的权值，仍然得到合法的分配方案。这是因为：点 u 出度为 0，将 u 的权值增大并不会影响 u 与其余节点的合法性；并且考虑去掉点 u 的其他节点，重新分配权值相当于对原来的权值进行离散化，不改变偏序关系。

因此，我们可以重新分配权值使得 u 的权值为 n。并且，由于 u > v，重新分配权值后答案的字典序减小。

由于点 u 的出度为 0，给它分配了最大的权值 n 之后，其余节点与 u 之间必然合法，只需要求出其余节点的最小字典序答案即可。因此将点 u 以及它的所有入边都删除，得到规模为 n-1 的子问题。又显然当 n=1 时，算法可以给出最小字典序答案，因此算法正确性得证。\square

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
#define likely(exp) __builtin_expect(!!(exp), 1)
#define unlikely(exp) __builtin_expect(!!(exp), 0)
using namespace std;
typedef long long ll;
const int N = 1e5+5; 

int n, m, deg[N], id[N], tms;
vector<int> e[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
void toposort() {
    priority_queue<int> q;
    rep(i, 1, n) if(!deg[i]) q.push(i);
    while(!q.empty()) {
        int u = q.top(); q.pop();
        id[u] = ++tms;
        for(int v : e[u]) if(!--deg[v]) q.push(v);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[v].push_back(u);
        ++deg[u];
    }
    toposort();
    rep(i, 1, n) printf("%d%c", n+1-id[i], " \n"[i==n]);
    return 0;
}