imicola 拓扑排序
拓扑排序

拓扑排序

436 字 · 约 1 分钟

拓扑排序是将偏序关系变化成线性关系的一种方法

如何进行拓扑排序?我们介绍 Kahn 算法

struct Kahn
{
    vint order;
    i64 n;
    Kahn(const vvint &g)
    {
        this->n = g.size();
        order.reserve(n);
        kahnsort(g);
    }
    void kahnsort(const vvint &g)
    {
        queue<i64> qu;
        vint indeg(n);
        for (i64 u = 1; u <= n; u++) {
            for (auto &&v : g[u]) {
                indeg[v]++;
            }
        }
        for (i64 i = 1; i <= n; i++) {
            if (indeg[i] == 0) qu.push(i);
        }
        while (!qu.empty()) {
            i64 u = qu.front();
            order.emplace_back(u);
            for (auto &&v : g[u]) {
                if (--indeg[v] == 0) qu.push(v);
            }
        }
    }
    vint get_order() const
    {
        return order;
    }
};
cpp

例题
Problem - C - 2143

对于这题,我们先疏通题意

题目给定我们一个树,数上每个边都关联两个贡献值x,yx,y,对于边(u,v)(u,v) 定义边的贡献值为:

{xif pu>pvyotherwise\begin{cases} x \qquad if\ p_{u} > p_{v} \\ y \qquad otherwise \end{cases}

其中pu,pvp_u,p_v需要我们如下定义,给定一个排列PP,将PP中每个数填入树中的节点上

我们需要确定一种排列,使整个树的贡献值最大

[!思路]
显然,因为我们获得的是一个排列,我们可以确定一种关系,让每一个边都可以获得较大的一个数,这实际上确定了一种偏序关系

所以我们便可以使用拓扑排序来确定线性关系,具体如下:

我们对树上每一个边从较小的节点向较大的节点建立有向边,最终形成有向图,最后我们对这个有向图拓扑排序即可

AC solution

void solve()
{
    i64 n;
    cin >> n;
    vint p(n + 1, 0);
    vector<vector<i64>> adj(n + 1);
    for (i64 i = 1; i < n; i++) {
        i64 u, v, x, y;
        cin >> u >> v >> x >> y;
        if (x > y) {
            adj[v].push_back(u);
            p[u]++;
        }
        else {
            adj[u].emplace_back(v);
            p[v]++;
        }
    }
    // 拓扑排序
    queue<i64> qu;
    for (i64 i = 1; i <= n; i++) {
        if (p[i] == 0) qu.push(i);
    }
    vint order;
    order.reserve(n);
    while (!qu.empty()) {
        i64 u = qu.front();
        qu.pop();
        order.push_back(u);
        for (auto &&i : adj[u]) {
            p[i]--;
            if (p[i] == 0) {
                qu.push(i);
            }
        }
    }
    vint res(n + 1);
    for (i64 i = 0; i < order.size(); i++) {
        res[order[i]] = i + 1;
    }
    for (i64 i = 1; i <= n; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
}
cpp