wordpress 导航网站,南通优化网站,网站运营成本,营销型网站开发营销文章目录 题目大意题解参考代码 题目大意 ( 0 ≤ a i ≤ 1 ) , ( 1 ≤ c o s t i ≤ 1 0 9 ) (0\leq a_i\leq 1),(1 \leq cost_i\leq 10^9) (0≤ai≤1),(1≤costi≤109)
题解
提供一种新的算法#xff0c;kruskal重构树。 该算法重新构树#xff0c;按边权排序每一条边… 文章目录 题目大意题解参考代码 题目大意 ( 0 ≤ a i ≤ 1 ) , ( 1 ≤ c o s t i ≤ 1 0 9 ) (0\leq a_i\leq 1),(1 \leq cost_i\leq 10^9) (0≤ai≤1),(1≤costi≤109)
题解
提供一种新的算法kruskal重构树。 该算法重新构树按边权排序每一条边后 新建一个点为“两边的节点所在最大节点”的父节点该点点权为该边边权。 该树有一些特征 ①是一个二叉树。 ③原节点全部为叶节点。 ②两个节点的LCA的点权就是其原最短路径的最大边权。 具体 Kruskal 算法学习 建树可以用并查集计算。 了解了这个算法我们再看问题要求最大边权这点可以用kruskal维护。 对于某个不为叶节点的节点 x x x 它左儿子与右儿子匹配的黑白节点的最大边权显然为 w x w_x wx 。 显然的我们可以枚举左右儿子节点中的黑白节点个数乘上点权即为该点的贡献。 我们发现答案可以通过 d f s dfs dfs 顺序从下往上来求解且不会造成前效性所以树形DP可以很好的解决这道题。 设 d p x , b dp_{x,b} dpx,b 表示在 x x x 的子树内有 b b b 个黑色节点的最优解。 d p x , b m a x ( d p s o n , b l a c k 1 d p s o n , b 2 w x ∗ ( b l a c k 1 ∗ w h i t e 2 b l a c k 2 ∗ w h i t e 1 ) ) dp_{x,b}max(dp_{son,black1}dp_{son,b2}w_x*(black1*white2black2*white1)) dpx,bmax(dpson,black1dpson,b2wx∗(black1∗white2black2∗white1)) white/black_1/2表示1/2的子树中有几个白色/黑色节点 且black1black2b 我们发现枚举 b b b 的黑白分布情况最多需要合并 m i n ( s u m s o n l , s u m s o n r ) min(sum_{sonl},sum_{sonr}) min(sumsonl,sumsonr)次 不然的话就需要从大的部分取一部分给数量少的一颗子树。 特殊的对于叶节点 d p x , b ( w x b ˆ 1 ) ∗ − c o s t x dp_{x,b}(w_xb \^\ 1)*-cost_x dpx,b(wxb ˆ1)∗−costx 剩下的就好处理多了写个DFS遍历一下即可处理。 计算时间复杂度对于kruskal重构树合并时长度最大为 l o g n log_n logn 即时间复杂度为 O ( N 2 l o g N ) O(N^2log_N) O(N2logN) 可以通过。
参考代码
#includebits/stdc.h
#define int long long
using namespace std;
const int N6e35;
const int inf1e187;
struct node{int x,y,w;
}f[N];
int fa[N],cost[N];
int w[N];
int n,m,t,ans;
int sonl[N],sonr[N];
int sum[N];
int dp[N][3000];
void dfs(int x)
{if(xn) //叶节点{dp[x][0](w[x]1)*(-cost[x]);dp[x][1](w[x]0)*(-cost[x]);
// coutx 0 dp[x][0]endl;
// coutx 1 dp[x][1]endl;sum[x]1;}else{dfs(sonl[x]);dfs(sonr[x]);int resmin(sum[sonl[x]],sum[sonr[x]]); //启发式合并平均复杂度为log_nsum[x]sum[sonl[x]]sum[sonr[x]];for(int i0;isum[sonl[x]];i)for(int j0;jsum[sonr[x]];j)dp[x][ij]-inf;for(int i0;isum[sonl[x]];i) //枚举黑色节点个数{for(int j0;jsum[sonr[x]];j) //DP转移{int sdp[sonl[x]][i]dp[sonr[x]][j]w[x]*(i*(sum[sonr[x]]-j)(sum[sonl[x]]-i)*j);dp[x][ij]max(dp[x][ij],s);ansmax(ans,dp[x][ij]);}} }
}
int cmp(node a,node b)
{return a.wb.w;
}
int sf(int x)
{if(fa[x]x)return x;return fa[x]sf(fa[x]);
}
signed main()
{cinn;for(int i1;in;i)scanf(%lld,w[i]);for(int i1;in;i)scanf(%lld,cost[i]);for(int i1;in;i)scanf(%lld%lld%lld,f[i].x,f[i].y,f[i].w);sort(f1,fn,cmp);tn;for(int i1;i2*n;i)fa[i]i;for(int i1;in;i) //kruskal构树{int xsf(f[i].x),ysf(f[i].y);fa[x]t;fa[y]t;w[t]f[i].w;sonl[t]x;sonr[t]y;}dfs(t);printf(%lld,ans);
}
