CF2143C：Max Tree题解

题目大意：

给定一个有

n

个节点的树，编号从

1

到

n

。每一条边包含了两个数

x

和

y

。
构造一个从

1

到

n

的排列

p

，其中

p_i

分配给节点

i

。
对于每条边

(u, v)

，其中

u < v

，会关联两个数

x

和

y

，这条边的贡献值的定义如下：

\begin{cases} x &\text{if } p_u < p_v, \\ y &\text{otherwise.} \end {cases}

整个树的值为每条边的值相加。
请求出使整个树的值最小的排列

p

。

思路

我想要每条边的值尽可能的小，但是又有一定约束性。赛时我就莫名联想到了差分约束，所以我就开始顺着这条线走下去。
对于图中的每个点，结合最小化贡献值，能够得到排列

p

中每一个元素的不等关系。于是想到：如果

x < y

，则在最小化贡献的情况下，

p_u

与

p_v

的大小关系应该是

p_u < p_v

。此时可以从

u

向

v

引一条有向边，表示

p_u < p_v

。否则就从

v

向

u

引一条有向边，表示

p_u > p_v

。称新产生的有向图为

g

。
可以发现，

g

是一个有向无环图。因为原图为一个树，而树本身无环。我们连接的边相当于给树的每一条边定一个方向，所以在此过程中也不会产生环。所以图

g

是一个有向无环图。于是我们就可以给图

g

进行拓扑排序。
在拓扑排序时，新建一个变量 nw = 1，表示现在是排列

p

的第几个数。每当访问一个点，就将这个点的答案赋值为 nw，随后 nw++ 即可。
文字可能有点难以理解，接下来是代码。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 150;
vector <int> e[200010];
void solve(){
    int n;
    cin >> n;
    vector <int> d(n + 1), ans(n + 1, 0);//动态数组，方便初始化
    for(int i = 1; i <= n; i++)//初始化边数组
        e[i].clear();
    for(int i = 1; i < n; i++){
        int u, v, x, y;
        cin >> u >> v >> x >> y;
        //根据题意，以及 x 和 y 的值，最小化边贡献
        if(x < y){
            d[v]++;
            e[u].push_back(v);
        }
        else{
            d[u]++;
            e[v].push_back(u);
        }
    }
    //以下是拓扑排序部分
    queue <int> q;
    int nw = 1;
    //将入度为 0 的节点入队
    for(int i = 1; i <= n; i++)
        if(!d[i])
            q.push(i), ans[i] = nw++;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto v : e[u])
            if(!--d[v]){
                //如果删去当前边后，弧头指向的节点入度为 0，则入队
                q.push(v);
                ans[v] = nw++;
            }
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " \n"[i == n];
}
int T;
int main(){
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

CF2143C：Max Tree题解

文章操作

CF2143C：Max Tree题解

题目大意：

思路

代码

相关推荐

评论

CF2143C：Max Tree题解