拓扑排序

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

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

A

kahn算法的主要思想是不断删除入度为0的节点并将其移除 具体步骤:

1. 统计每个节点的入度
2. 将所有入度为0的点加入队列
3. 不断的从队列中取出节点

• 将其加入结果序列
• 对其所有出边的目标节点入度减1
• 如目标节点入度为0,则入队

4. 如果最终结果包括所有节点，则说明排序完成，否则说明图中有环

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;
    }
};

例题 Problem - C - 2143

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

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

$$\{\begin{array}{l}xif{p}_u>p_v\\ yotherwise\end{array}$$

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

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

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

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

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

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;
}