【CF2021E】Digital Village（All Version）

题目

给你一张 $n$ 个点 $m$ 条边的无向图，有 $p$ 个关键点。你需要选择 $k$ 个点染黑，使得这 $p$ 个关键点到这 $k$ 个黑点的代价和最小。定义代价为两点之间边权最大的边的最小值。
你需要求出 k = 1,2,…,n 的所有答案

E1 n,m,p<=400
E2 n,m,p<=5000
E3 n,m,p<=2e5

传送门

E1 & E2

两点之间最大边权最小值让你想到了什么？最小生成树。
但是这玩意直接在最小生成树上也不好做啊。但是如果是 kruskal 重构树呢？
显然，两个点 $(u,v)$ 之间的代价就是重构树上的 $va{l}_{lca(u,v)}$。
这样我们就可以愉快的dp啦！

设 $d{p}_{u,i}$ 为以 $u$ 为根的子树，染黑了 $i$ 个关键点的最小代价。
转移要讨论这棵树有没有染黑任何一个点，如果没有的话整棵树的代价就是 $siz\times val$，其中 $siz$ 为子树内关键点的个数。
做个树上背包就行啦。时间复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353;
int n,m,k;
vector<bool> bz;
vector<int> val,fa,siz;
vector<vector<int>> e,dp;
int gf(int x)
{
return x==fa[x]?x:fa[x]=gf(fa[x]);
}
void dfs(int u,int fa)
{
dp[u].assign(1,inf);
if(bz[u])
{
siz[u]=1;
dp[u].push_back(0);
}
for(auto v:e[u])
{
if(v==fa) continue;
dfs(v,u);
vector<int> dpn(siz[u]+siz[v]+1,inf);
for(int i=1; i<=siz[u]+siz[v]; i++)
{
for(int j=max(0ll,i-siz[u]); j<=min(i,siz[v]); j++)
{
if(j==0)
{
dpn[i]=min(dpn[i],dp[u][i-j]+val[u]*siz[v]);
}
else if(i==j)
{
dpn[i]=min(dpn[i],dp[v][j]+val[u]*siz[u]);
}
else
{
dpn[i]=min(dpn[i],dp[u][i-j]+dp[v][j]);
}
}
}
siz[u]+=siz[v];
dp[u]=dpn;
}
}
void O_o()
{
cin>>n>>m>>k;
bz.assign(2*n,0);
for(int i=1; i<=k; i++)
{
int x;
cin>>x;
bz[x]=1;
}
vector<array<int,3>> edge;//l,x,y
for(int i=1; i<=m; i++)
{
int x,y,l;
cin>>x>>y>>l;
edge.push_back({l,x,y});
}
sort(edge.begin(),edge.end());
fa.assign(2*n,0);
for(int i=1; i<=2*n; i++) fa[i]=i;
int rt=n;
e.assign(2*n,vector<int>());
val.assign(2*n,0);
for(auto [l,x,y]:edge)
{
int u=gf(x),v=gf(y);
if(u==v) continue;
rt++;
fa[u]=rt;
fa[v]=rt;
val[rt]=l;
e[rt].push_back(u);
e[rt].push_back(v);
}
dp.assign(2*n,vector<int>());
siz.assign(2*n,0);
dfs(rt,0);
for(int i=1; i<=min(k,n); i++)
cout<<dp[rt][i]<<" ";
for(int i=k+1; i<=n; i++)
cout<<"0 ";
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(12);
int T=1;
cin>>T;
while(T--)
{
O_o();
}
}

这个树上背包似乎很难继续优化了呢。我们必须从题目更深的性质去思考问题。
在解决 E3 之前，我们不妨先看一下这道题：

CCPC2024 山东邀请赛 F

这是一道签到题。
可以发现，这个式子可以拆成 $k$ 段后缀和之和，并且其中一段后缀和必须是整个序列。
所以直接把后缀和排个序，选出前 $k-1$ 大的后缀和，再加上整个序列的和即可。

E3

在题目中，一个点都不染色是不合法的，代价应该为 $inf$，但这不利于我们解题。
我们不妨假设他们每一条路径都经过了最大的那条边，也就是初始答案 $ans=si{z}_{rt}\ast va{l}_{rt}$
把样例的重构树画出来，观察一下染黑了一个叶子，对答案会有什么影响？
不太好看出来？由那道签到题的启发，给 $val$ 做个树上差分试试？
可以发现，从叶子结点到根的那条路径上，$va{l}_{fa}-va{l}_u$ 的计算次数都被减少了 $si{z}_u$
再染一个点试试？可以发现，从叶子结点，一直到已经被选择过的那条链为止，$va{l}_{fa}-va{l}_u$ 的计算次数都被减少了 $si{z}_u$。
问题就转换成了，你要在树上选出减少答案前 $k$ 大，互不相交的链。
是不是很像树链剖分？
没错，我们把 $(va{l}_{fa}-va{l}_u)\ast si{z}_u$ 作为 $(u,f{a}_u)$ 的边权，对整棵树做长链剖分（jiangly：这是典中典长链剖分题）。
把所有的长链的权值排序，然后每次选出前 $k$ 大减去就做完啦！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353;
int n,m,k;
vector<bool> bz;
vector<int> val,fa,siz,p;
vector<vector<int>> e;
int gf(int x)
{
return x==fa[x]?x:fa[x]=gf(fa[x]);
}
int dfs(int u,int fa)
{
if(bz[u])
{
siz[u]=1;
}
int mx=0;
for(auto v:e[u])
{
int res=dfs(v,u);
siz[u]+=siz[v];
if(mx<res)
swap(res,mx);
p.push_back(res);
}
if(fa!=0)
mx+=siz[u]*(val[fa]-val[u]);
return mx;
}
void O_o()
{
cin>>n>>m>>k;
bz.assign(2*n,0);
for(int i=1; i<=k; i++)
{
int x;
cin>>x;
bz[x]=1;
}
vector<array<int,3>> edge;//l,x,y
for(int i=1; i<=m; i++)
{
int x,y,l;
cin>>x>>y>>l;
edge.push_back({l,x,y});
}
sort(edge.begin(),edge.end());
fa.assign(2*n,0);
for(int i=1; i<=2*n; i++) fa[i]=i;
int rt=n;
e.assign(2*n,vector<int>());
val.assign(2*n,0);
for(auto [l,x,y]:edge)
{
int u=gf(x),v=gf(y);
if(u==v) continue;
rt++;
fa[u]=rt;
fa[v]=rt;
val[rt]=l;
e[rt].push_back(u);
e[rt].push_back(v);
}
siz.assign(2*n,0);
p.clear();
p.push_back(dfs(rt,0));
int ans=k*val[rt];
sort(p.begin(),p.end(),greater<>());
for(int i=0; i<n; i++)
{
ans-=p[i];
cout<<ans<<" ";
}
cout<<"\n";
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<<fixed<<setprecision(12);
int T=1;
cin>>T;
while(T--)
{
O_o();
}
}

原文地址：https://blog.csdn.net/Eric1561759334/article/details/142738794

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！