AcWing 511:联合权值 ← DFS、链式前向星

2023-12-03 10:01

本文主要是介绍AcWing 511:联合权值 ← DFS、链式前向星,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目来源】
https://www.acwing.com/problem/content/513/

【题目描述】

无向连通图 G 有 n 个点,n−1 条边。
点从 1 到 n 依次编号,编号为 i 的点的权值为 Wi,每条边的长度均为 1。
图上两点 (u,v) 的距离定义为 u 点到 v 点的
最短距离
对于图 G 上的点对 (u,v),若它们的距离为 2,则它们之间会产生 Wu×Wv 的
联合权值
请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?

【输入格式】
第一行包含 1 个整数 n。
接下来 n−1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和编号为 v 的点之间有边相连。
最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。

【输出格式】
输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值的最大值和所有联合权值之和。
由于所有联合权值之和可能很大,输出它时要对 10007 取余。

【数据范围】
1<n≤200000,
0<Wi≤10000

【输入样例】
5
1 2
2 3
3 4
4 5
1 5 2 3 10

【输出样例】
20 74

【算法分析】
本例代码,采用
链式前向星存无向图,并基于此进行无向图的深度优先搜索。详见:
https://blog.csdn.net/hnjzsyjyj/article/details/119917795
链式前向星的相关介绍可参考:

https://blog.csdn.net/hnjzsyjyj/article/details/119917795
https://blog.csdn.net/hnjzsyjyj/article/details/127190456
https://blog.csdn.net/hnjzsyjyj/article/details/126474608

【算法代码】
代码来源于:
https://www.acwing.com/solution/content/3516/

/* 链式前向星存图
val[idx] 表示第 idx 条边的权值。
e[idx] 表示第 idx 条边的终点。
ne[idx] 表示与第 idx 条边同起点的最近一次被添加的边的编号。
h[a] 表示以结点 a 为起点的最近一次被添加的边的编号。这个表述是在使用 ne[idx]=h[a] 时,也即使用 h[a]=idx++ 更新 h[a] 之前而言的。要特别注意这个语境。
*/#include <bits/stdc++.h>
using namespace std;const int N=2e5+5;
const int M=N<<1;
const int mod=10007;int n;
int h[N],e[M],ne[M],idx;
int w[N];
int f[N],g[N];
int imax, isum;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u, int father) {int sum=0, maxv=0;for(int i=h[u]; ~i; i=ne[i]) { //~i; equivalent to i!=-1;int j=e[i];if(j!=father) {dfs(j,u);imax=max(imax,w[u]*f[j]);imax=max(imax,maxv*w[j]);maxv=max(maxv,w[j]);isum=(isum+w[u]*g[j])%mod;isum=(isum+sum*w[j])%mod;sum=(sum+w[j])%mod;f[u]=max(f[u],w[j]);g[u]=(g[u]+w[j])%mod;}}
}int main() {scanf("%d",&n);memset(h,-1,sizeof(h));for(int i=0; i<n-1; i++) {int a,b;scanf("%d %d",&a,&b);add(a,b),add(b,a);}for(int i=1; i<=n; i++) scanf("%d",&w[i]);dfs(1,-1);printf("%d %d\n",imax,2*isum%mod);return 0;
}/*
in:
5
1 2
2 3
3 4
4 5
1 5 2 3 10out:
20 74
*/





【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119917795
https://www.acwing.com/solution/content/3516/
https://blog.csdn.net/hnjzsyjyj/article/details/127190456
https://blog.csdn.net/hnjzsyjyj/article/details/126474608





 

这篇关于AcWing 511:联合权值 ← DFS、链式前向星的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/449024

相关文章

python与QT联合的详细步骤记录

《python与QT联合的详细步骤记录》:本文主要介绍python与QT联合的详细步骤,文章还展示了如何在Python中调用QT的.ui文件来实现GUI界面,并介绍了多窗口的应用,文中通过代码介绍... 目录一、文章简介二、安装pyqt5三、GUI页面设计四、python的使用python文件创建pytho

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

ural 1149. Sinus Dances dfs

1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let  An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let  Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given  N print  SN Input One

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

Java 后端接口入参 - 联合前端VUE 使用AES完成入参出参加密解密

加密效果: 解密后的数据就是正常数据: 后端:使用的是spring-cloud框架,在gateway模块进行操作 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>30.0-jre</version></dependency> 编写一个AES加密

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

C和指针:结构体(struct)和联合(union)

结构体和联合 结构体 结构体包含一些数据成员,每个成员可能具有不同的类型。 数组的元素长度相同,可以通过下标访问(转换为指针)。但是结构体的成员可能长度不同,所以不能用下标来访问它们。成员有自己的名字,可以通过名字访问成员。 结构声明 在声明结构时,必须列出它包含的所有成员。 struct tag {member-list} variable-list ; 定义一个结构体变量x(包含

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿

[数据结构]栈之链式栈的类模板实现

栈的抽象基类的实现:(不用抽象基类也是可以的,为了使用虚函数方便) #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virtual bool Pop(T& x)=0;virtual b