建站公司最新报价,网店设计是做什么的,wordpress插件怎么汉化,域名转出过程网站能打开吗题目
给你一张 n n n 个点 m m m 条边的无向图#xff0c;有 p p p 个关键点。你需要选择 k k k 个点染黑#xff0c;使得这 p p p 个关键点到这 k k k 个黑点的代价和最小。定义代价为两点之间边权最大的边的最小值。 你需要求出 k 1,2,…,n 的所有答案
E1 n,m,p有 p p p 个关键点。你需要选择 k k k 个点染黑使得这 p p p 个关键点到这 k k k 个黑点的代价和最小。定义代价为两点之间边权最大的边的最小值。 你需要求出 k 1,2,…,n 的所有答案
E1 n,m,p400 E2 n,m,p5000 E3 n,m,p2e5
传送门
E1 E2
两点之间最大边权最小值让你想到了什么最小生成树。 但是这玩意直接在最小生成树上也不好做啊。但是如果是 kruskal 重构树呢 显然两个点 ( u , v ) (u,v) (u,v) 之间的代价就是重构树上的 v a l l c a ( u , v ) val_{lca(u,v)} vallca(u,v)。 这样我们就可以愉快的dp啦
设 d p u , i dp_{u,i} dpu,i 为以 u u u 为根的子树染黑了 i i i 个关键点的最小代价。 转移要讨论这棵树有没有染黑任何一个点如果没有的话整棵树的代价就是 s i z × v a l siz\times val siz×val其中 s i z siz siz 为子树内关键点的个数。 做个树上背包就行啦。时间复杂度 O ( n 2 ) O(n^2) O(n2)
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e67,inf1e18,mod998244353;
int n,m,k;
vectorbool bz;
vectorint val,fa,siz;
vectorvectorint e,dp;
int gf(int x)
{return xfa[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(vfa) continue;dfs(v,u);vectorint dpn(siz[u]siz[v]1,inf);for(int i1; isiz[u]siz[v]; i){for(int jmax(0ll,i-siz[u]); jmin(i,siz[v]); j){if(j0){dpn[i]min(dpn[i],dp[u][i-j]val[u]*siz[v]);}else if(ij){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()
{cinnmk;bz.assign(2*n,0);for(int i1; ik; i){int x;cinx;bz[x]1;}vectorarrayint,3 edge;//l,x,yfor(int i1; im; i){int x,y,l;cinxyl;edge.push_back({l,x,y});}sort(edge.begin(),edge.end());fa.assign(2*n,0);for(int i1; i2*n; i) fa[i]i;int rtn;e.assign(2*n,vectorint());val.assign(2*n,0);for(auto [l,x,y]:edge){int ugf(x),vgf(y);if(uv) 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,vectorint());siz.assign(2*n,0);dfs(rt,0);for(int i1; imin(k,n); i)coutdp[rt][i] ;for(int ik1; in; i)cout0 ;cout\n;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(12);int T1;cinT;while(T--){O_o();}
}
这个树上背包似乎很难继续优化了呢。我们必须从题目更深的性质去思考问题。 在解决 E3 之前我们不妨先看一下这道题
CCPC2024 山东邀请赛 F 这是一道签到题。 可以发现这个式子可以拆成 k k k 段后缀和之和并且其中一段后缀和必须是整个序列。 所以直接把后缀和排个序选出前 k − 1 k-1 k−1 大的后缀和再加上整个序列的和即可。
E3
在题目中一个点都不染色是不合法的代价应该为 i n f inf inf但这不利于我们解题。 我们不妨假设他们每一条路径都经过了最大的那条边也就是初始答案 a n s s i z r t ∗ v a l r t anssiz_{rt}*val_{rt} anssizrt∗valrt 把样例的重构树画出来观察一下染黑了一个叶子对答案会有什么影响 不太好看出来由那道签到题的启发给 v a l val val 做个树上差分试试 可以发现从叶子结点到根的那条路径上 v a l f a − v a l u val_{fa}-val_{u} valfa−valu 的计算次数都被减少了 s i z u siz_u sizu 再染一个点试试可以发现从叶子结点一直到已经被选择过的那条链为止 v a l f a − v a l u val_{fa}-val_{u} valfa−valu 的计算次数都被减少了 s i z u siz_u sizu。 问题就转换成了你要在树上选出减少答案前 k k k 大互不相交的链。 是不是很像树链剖分 没错我们把 ( v a l f a − v a l u ) ∗ s i z u (val_{fa}-val_{u})*siz_u (valfa−valu)∗sizu 作为 ( u , f a u ) (u,fa_u) (u,fau) 的边权对整棵树做长链剖分jiangly这是典中典长链剖分题。 把所有的长链的权值排序然后每次选出前 k k k 大减去就做完啦
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e67,inf1e18,mod998244353;
int n,m,k;
vectorbool bz;
vectorint val,fa,siz,p;
vectorvectorint e;
int gf(int x)
{return xfa[x]?x:fa[x]gf(fa[x]);
}
int dfs(int u,int fa)
{if(bz[u]){siz[u]1;}int mx0;for(auto v:e[u]){int resdfs(v,u);siz[u]siz[v];if(mxres)swap(res,mx);p.push_back(res);}if(fa!0)mxsiz[u]*(val[fa]-val[u]);return mx;
}
void O_o()
{cinnmk;bz.assign(2*n,0);for(int i1; ik; i){int x;cinx;bz[x]1;}vectorarrayint,3 edge;//l,x,yfor(int i1; im; i){int x,y,l;cinxyl;edge.push_back({l,x,y});}sort(edge.begin(),edge.end());fa.assign(2*n,0);for(int i1; i2*n; i) fa[i]i;int rtn;e.assign(2*n,vectorint());val.assign(2*n,0);for(auto [l,x,y]:edge){int ugf(x),vgf(y);if(uv) 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 ansk*val[rt];sort(p.begin(),p.end(),greater());for(int i0; in; i){ans-p[i];coutans ;}cout\n;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(12);int T1;cinT;while(T--){O_o();}
}
