Codeforces Round 977 (Div. 2) E. Digital Village（树形背包 kruskal重构树凸函数闵可夫斯基和(min,+)差分优化）

小衣同学

已于 2024-10-07 10:27:10 修改

阅读量1.3k

点赞数 24

分类专栏： # dp优化 # 树形dp/换根dp/长链剖分文章标签：树形dp kruskal重构树闵可夫斯基和差分凸函数

于 2024-10-07 02:38:27 首次发布

本文链接：https://blog.csdn.net/Code92007/article/details/142734416

版权

树形dp/换根dp/长链剖分同时被 2 个专栏收录

30 篇文章

订阅专栏

dp优化

15 篇文章

订阅专栏

题目

n点m边的图，有p个点需要上网，可以在一些点上装服务器，

上网点x到服务器y的延迟，是一条x到y路径上的边权的最大值，

最优延迟，是所有x到y的路径里，使最大值最小的那个延迟

对于k=1,2，...，n，确定恰好装k个服务器时，p个点的最小总延迟之和

easy：n=400

hard：n=5000

extreme：n=2e5

思路来源

lzz、zeeman、jiangly代码

闵可夫斯基和与凸函数优化

闵可夫斯基和学习笔记 - HappyJaPhy - 博客园

【学习笔记】Max 卷积 & 闵可夫斯基和 - APJifengc - 博客园

题解

因为是边权最大值，不难想到按边权从小到大排序维护

先考虑easy & hard，

如果我对于每个连通块维护装1,2,...,x个服务器时，能满足连通块内所有上网点的最小总延迟之和

那么kruskal求最小生成树，连接一条生成树边时，

计u是左连通块的祖先，v是右连通块的祖先，w是这条边的权值，

只有以下可能：

①没有上网点需要跨过w这条边，

左连通块装x个服务器，右连通块装y个服务器，

总共装x+y个，转移就是树形背包的合并

②有上网点需要跨过w这条边，因为w是当前考虑到的最大边，

所以只能是其中一个连通块里没有装服务器，

全跑到另一个连通块里用服务器，那么讨论一下是u没有还是v没有

直接暴力每次开n大小的vector时复杂度是O(n^3)的，

但是用树形背包的trick，开大小是连通块大小的vector，复杂度就是O(n^2)的了，

可以参考https://leetcode.cn/circle/discuss/t7l62c/

当然easy还有一种做法是，先floyd求出上网点x到服务器y的最大边的最小值dis[x][y]

然后类似prim，由f(i)去推f(i+1)，每次新找一个最优的服务器点

只是这种做法无法扩展到O(n^2)

然后考虑extreme，树形背包转移是经典的凸函数优化的式子，实际就是在维护凸函数

可以参考上面提到的博客，

简单来说，就是两个凸包的闵可夫斯基和(min/max,+)卷积还是凸包

形如h[i][z]=min(f[u][x]+g[v][y]+F(u,v)，x+y=z)这种式子，

在f、g、F是凸函数的前提下，可以通过差分+排序优化复杂度

本题中可以感性理解下凸函数，随着服务器的增多，每次能优化的边权越来越少

然后考虑做法，先在kruskal求生成树的过程中，把kruskal重构树建出来，

在kruskal重构树上dp，

dp[x]表示（x所在连通块里本来没有服务器）如果有装一个服务器的机会，装在x这个连通块里，使得x里的所有上网点，不再需要通过x的父亲fa[x]对应的原图的边进到另一个连通块里时，可以节省的最大权值之和是多少

设kruskal重构树上点x有直连儿子y1、y2

假设y1内子树所有点都在y1处集结（已经通过y1及子树内的边联通），

如果有一个服务器在y1所在的连通块里，

就能阻止y1子树内所有点通过点x进入兄弟y2子树，

也就是x这条边权实际不需要连，也就是能省去y1->x增量的贡献

递归往y1的子树里考虑，放的这一个服务器，

可以满足既在y1连通块里，也在y1直连儿子z1的连通块里，

这样就能省去z1->y1增量的贡献，

在z1和z2两个儿子中，取dp值二者更大的那个儿子显然更优

所以先往下搜求得儿子的结果，再回溯的时候由父亲决策选哪个儿子

递归到底实际是一个叶子，也就是原图上的点

所以放一个服务器时，影响的是一条权值和最大的链，

将dp值更大的儿子看成是重儿子，可以将树解构成若干条重链，

那么将kruskal重构树树链剖分后，按权值链降序贪心即可

每一条链都对应了加一个服务器时，可以省去的代价

hard代码（树形背包）

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
const ll INF=1e15;
const int N=5e3+10;
int t,n,m,p,v,par[N],ans[N],sz[N],now;
vector<ll>f[N],dp[N];
bool ok[N];
struct edge{
    int u,v,w;
}e[N];
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
bool operator<(edge a,edge b){
    return a.w<b.w;
}
int main(){
    sci(t);
    while(t--){
        sci(n),sci(m),sci(p);
        rep(i,1,n){
            par[i]=i;
            sz[i]=0;
            dp[i].resize(2,0);
        }
        rep(i,1,p){
            sci(v);
            ok[v]=1;
            sz[v]=1;
            dp[v][1]=0;
            dp[v][0]=INF;
        }
        //now=p;
        //per(i,n,now)ans[i]=0;
        rep(i,1,m){
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        }
        sort(e+1,e+m+1);
        rep(i,1,m){
            int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
            if(u==v)continue;
            vector<ll>tmp(sz[u]+sz[v]+1,INF);
            rep(x,0,sz[u]){
                rep(y,0,sz[v]){
                    tmp[x+y]=min(tmp[x+y],dp[u][x]+dp[v][y]);
                    if(!x && !y)continue;
                    if(!x)tmp[y]=min(tmp[y],dp[v][y]+1ll*sz[u]*w);
                    if(!y)tmp[x]=min(tmp[x],dp[u][x]+1ll*sz[v]*w);
                }
            }
            dp[u]=tmp;
            sz[u]+=sz[v];
            par[v]=u;
        }
        int f=find(1);
        rep(i,1,n){
            printf("%lld%c",i>=p?0:dp[f][i]," \n"[i==n]);
        }
    }
    return 0;
}

/*
dp[i][j]
*/

extreme代码（kruskal重构树凸函数优化差分贪心）

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=4e5+10;
const ll INF=1e15;
int t,n,m,p,v,c,par[M],sz[M],W[M];
ll ans,dp[M];
vector<ll>f[M];
struct edge{
    int u,v,w;
}e[N];
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
bool operator<(edge a,edge b){
    return a.w<b.w;
}
void dfs(int u,int fa){
    dp[u]=0;
    for(auto &v:f[u]){
        dfs(v,u);
        dp[u]=max(dp[u],dp[v]);
    }
    for(auto &v:f[u]){
        if(dp[u]==dp[v]){
            dp[v]=0;
            break;
        }
    }
    if(u<c){
        dp[u]+=1ll*sz[u]*(W[fa]-W[u]);
    }
}
int main(){
    sci(t);
    while(t--){
        sci(n),sci(m),sci(p);
        rep(i,1,n){
            par[i]=i;
            sz[i]=W[i]=0;
        }
        rep(i,1,p){
            sci(v);
            sz[v]=1;
        }
        rep(i,1,m){
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        }
        sort(e+1,e+m+1);
        c=n;
        rep(i,1,m){
            int u=find(e[i].u),v=find(e[i].v),w=e[i].w;
            if(u==v)continue;
            W[++c]=w;sz[c]=0;
            par[u]=par[v]=par[c]=c;
            f[c].pb(u);
            f[c].pb(v);
            sz[c]=sz[u]+sz[v];
        }
        dfs(c,0);
        ll ans=1ll*p*W[c];
        sort(dp+1,dp+c+1,greater<ll>());
        rep(i,1,n){
            ans-=dp[i];
            printf("%lld%c",ans," \n"[i==n]);
        }
        rep(i,1,c){
            f[i].clear();
        }
    }
    return 0;
}
/*
设kruskal重构树上点x有直连儿子y1、y2

假设y1内子树所有点都在y1处集结（已经通过y1及子树内的边联通），
如果有一个宽带在y1所在的连通块里，
就能阻止y1子树内所有点通过点x进入兄弟y2子树，
也就是x这条边权实际不需要连，也就是能省去y1->x增量的贡献

递归往下考虑，放的这一个宽带，
可以满足既在y1连通块里，也在y1直连儿子z1的连通块里，
这样就能省去z1->y1增量的贡献，取二者更大的那个显然更优，

递归到底实际是一个叶子，也就是原图上的点
所以放一个宽带最优影响的是一条权值和最大的重链
那么将kruskal重构树树链剖分后，按权值链降序贪心即可

由于实际转移是一个树形背包的形式，函数也都是凸函数，
所以闵可夫斯基和(min,+)卷积可以被拆成差分，即f(i+1)可以由f(i)得到
*/