题解 P6943【[ICPC2018 WF]Conquer The World】

· · 题解

P6943 [ICPC2018 WF]Conquer The World解题报告：

更好的阅读体验

题意

给定一个 n 个点的带点边权的树（设点权为 v），可以任意将点的点权在树上进行移动，移动单位点权的代价为路径上的边权和，求让所有点点权非负的最小代价。

1\leqslant n\leqslant 2.5\times 10^5,\sum v\geqslant 0,\sum[v>0]v\leqslant 10^6

分析

小清新题。

下面称正点权点为源，负点权点为汇。

首先有一个明显的费用流做法，直接源点连正点权，负点权连汇点然后费用流即可。

我们可以发现一个性质，对于匹配的两条路径，它们交叉的代价一定不优于它们不交叉的代价。

于是可以考虑反悔贪心（模拟费用流），设当前子树的根为 x，那么：

贪心策略：每次找到深度最小的源和深度最小的汇进行匹配。

反悔策略：将源的点权改成 2dep_x 减去汇的点权，将汇的点权改成 2dep_x- 减去源的点权即可，容易发现这样匹配之后可以取消掉这对源汇的匹配。

使用左偏树来支持堆的合并即可，时间复杂度 O(\sum|v|\log(\sum|v|))。

代码

直接用了 pbds 来实现左偏树。

AC 记录

#include<stdio.h>
#include<vector>
#include<ext/pb_ds/priority_queue.hpp>
#define inf 1000000000000
using namespace std;
const int maxn=250005;
int n,tot;
int a[maxn],b[maxn];
long long ans;
long long dep[maxn];
vector< pair<int,int> >v[maxn];
__gnu_pbds::priority_queue< long long,greater<long long> >A[maxn],B[maxn];
void dfs(int x,int last){
    for(int i=a[x]+1;i<=b[x];i++)
        A[x].push(dep[x]-inf),tot++;
    for(int i=b[x]+1;i<=a[x];i++)
        B[x].push(dep[x]);
    for(int i=0;i<v[x].size();i++){
        int y=v[x][i].first,z=v[x][i].second;
        if(y!=last)
            dep[y]=dep[x]+z,dfs(y,x),A[x].join(A[y]),B[x].join(B[y]);
    }
    while(!A[x].empty()&&!B[x].empty()&&A[x].top()+B[x].top()-2*dep[x]<0){
        long long u=A[x].top(),v=B[x].top();
        A[x].pop(),B[x].pop(),ans+=u+v-2*dep[x];
        A[x].push(2*dep[x]-v),B[x].push(2*dep[x]-u);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,x,y,z;i<n;i++)
        scanf("%d%d%d",&x,&y,&z),v[x].push_back(make_pair(y,z)),v[y].push_back(make_pair(x,z));
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    dfs(1,0);
    printf("%lld\n",ans+1ll*tot*inf);
    return 0;
}