首页 > 其他分享 >2023-10-04:用go语言,现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号 给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges , 其中 edge

2023-10-04:用go语言,现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号 给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges , 其中 edge

时间:2023-10-04 16:22:41浏览次数:41  
标签:10 cur 04 int graph 整数 trips uf 节点

2023-10-04:用go语言,现有一棵无向、无根的树,树中有 n 个节点,按从 0 到 n - 1 编号

给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ,

其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ,其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ,其中 trips[i] = [starti, endi] 表示

从节点 starti 开始第 i 次旅行,并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前,你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

输入:n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]。

输出:23。

来自左程云

答案2023-10-04:

大体过程如下:

1.构建图:根据输入的edges构建无向图,使用邻接表存储每个节点的邻居节点。

2.初始化查询数组:根据trips初始化查询数组,将每个旅行的起点和终点加入到对应节点的查询数组中。

3.初始化并查集:初始化一个并查集,用于保存节点的父节点信息和标签。将每个节点的父节点初始化为自身,标签初始化为-1。

4.进行Tarjan算法:从根节点开始遍历树,使用递归的方式进行深度优先搜索。

  • 对于每个节点cur,记录其父节点father。

  • 遍历cur的邻居节点next,如果next不等于father,进行递归操作。

  • 递归操作结束后,将cur和next节点合并,设置它们的标签为cur。

  • 对于cur节点的查询数组中的每个查询,如果查询的终点的标签不为-1,说明该查询经过cur节点,记录查询的终点标签为最低公共祖先节点。

5.计算每个节点的旅行个数:遍历旅行数组,统计每个节点作为起点或终点的旅行个数。

  • 对于每个旅行,起点和终点的旅行个数加1,最低公共祖先节点的旅行个数减1。

  • 如果最低公共祖先节点的父节点不为-1,最低公共祖先节点的父节点的旅行个数减1。

6.使用深度优先搜索计算价格总和:从根节点开始,使用递归的方式进行深度优先搜索。

  • 对于每个节点cur,计算不选择减半价格的情况下的总价格no和选择减半价格的情况下的总价格

  • 遍历cur的邻居节点next,如果next不等于father,进行递归操作。

  • 更新no和yes的值。

7.返回最小价格总和:取no和yes中较小的值作为最小价格总和。

总的时间复杂度:O(n)(遍历节点和邻居节点) + O(m)(遍历查询数组) + O(n)(遍历旅行数组) + O(n)(遍历节点和邻居节点) = O(n + m)

总的额外空间复杂度:O(n)(存储图) + O(m)(存储查询数组) + O(n)(存储父节点信息) + O(n)(存储旅行个数) + O(n)(存储价格总和) = O(n + m)

go完整代码如下:

package main

import (
	"fmt"
	"math"
)

func minimumTotalPrice(n int, edges [][]int, price []int, trips [][]int) int {
	graph := make([][]int, n)
	queries := make([][][]int, n)
	for i := 0; i < n; i++ {
		graph[i] = make([]int, 0)
		queries[i] = make([][]int, 0)
	}
	for _, edge := range edges {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		graph[edge[1]] = append(graph[edge[1]], edge[0])
	}
	m := len(trips)
	lcs := make([]int, m)
	for i := 0; i < m; i++ {
		if trips[i][0] == trips[i][1] {
			lcs[i] = trips[i][0]
		} else {
			queries[trips[i][0]] = append(queries[trips[i][0]], []int{trips[i][1], i})
			queries[trips[i][1]] = append(queries[trips[i][1]], []int{trips[i][0], i})
		}
	}
	uf := &UnionFind{}
	uf.init(n)
	fathers := make([]int, n)
	tarjan(graph, 0, -1, uf, queries, fathers, lcs)
	cnts := make([]int, n)
	for i := 0; i < m; i++ {
		cnts[trips[i][0]]++
		cnts[trips[i][1]]++
		cnts[lcs[i]]--
		if fathers[lcs[i]] != -1 {
			cnts[fathers[lcs[i]]]--
		}
	}
	dfs(graph, 0, -1, cnts)
	ans := dp(graph, 0, -1, cnts, price)
	return int(math.Min(float64(ans[0]), float64(ans[1])))
}

func tarjan(graph [][]int, cur int, father int, uf *UnionFind, queries [][][]int, fathers []int, lcs []int) {
	fathers[cur] = father
	for _, next := range graph[cur] {
		if next != father {
			tarjan(graph, next, cur, uf, queries, fathers, lcs)
			uf.union(cur, next)
			uf.setTag(cur, cur)
		}
	}
	for _, query := range queries[cur] {
		tag := uf.getTag(query[0])
		if tag != -1 {
			lcs[query[1]] = tag
		}
	}
}

func dfs(graph [][]int, cur int, father int, cnts []int) {
	for _, next := range graph[cur] {
		if next != father {
			dfs(graph, next, cur, cnts)
			cnts[cur] += cnts[next]
		}
	}
}

func dp(graph [][]int, cur int, father int, cnts []int, price []int) []int {
	no := price[cur] * cnts[cur]
	yes := (price[cur] / 2) * cnts[cur]
	for _, next := range graph[cur] {
		if next != father {
			nextAns := dp(graph, next, cur, cnts, price)
			no += int(math.Min(float64(nextAns[0]), float64(nextAns[1])))
			yes += nextAns[0]
		}
	}
	return []int{no, yes}
}

type UnionFind struct {
	father []int
	size   []int
	tag    []int
	help   []int
}

func (uf *UnionFind) init(n int) {
	uf.father = make([]int, n)
	uf.size = make([]int, n)
	uf.tag = make([]int, n)
	uf.help = make([]int, n)
	for i := 0; i < n; i++ {
		uf.father[i] = i
		uf.size[i] = 1
		uf.tag[i] = -1
	}
}

func (uf *UnionFind) find(i int) int {
	size := 0
	for i != uf.father[i] {
		uf.help[size] = i
		i = uf.father[i]
		size++
	}
	for size > 0 {
		size--
		uf.father[uf.help[size]] = i
	}
	return i
}

func (uf *UnionFind) union(i, j int) {
	fi := uf.find(i)
	fj := uf.find(j)
	if fi != fj {
		if uf.size[fi] >= uf.size[fj] {
			uf.father[fj] = fi
			uf.size[fi] += uf.size[fj]
		} else {
			uf.father[fi] = fj
			uf.size[fj] += uf.size[fi]
		}
	}
}

func (uf *UnionFind) setTag(i, t int) {
	uf.tag[uf.find(i)] = t
}

func (uf *UnionFind) getTag(i int) int {
	return uf.tag[uf.find(i)]
}

func main() {
	n := 4
	edges := [][]int{{0, 1}, {1, 2}, {1, 3}}
	price := []int{2, 2, 10, 6}
	trips := [][]int{{0, 3}, {2, 1}, {2, 3}}
	result := minimumTotalPrice(n, edges, price, trips)
	fmt.Println(result)
}

在这里插入图片描述

标签:10,cur,04,int,graph,整数,trips,uf,节点
From: https://www.cnblogs.com/moonfdd/p/17742404.html

相关文章

  • 2023.10.4测试
    T1最短路T2欧拉函数给定常数\(B\),\(T\)组测试数据,每次给定\(l,r\),求\[\sum_{x=l}^r\varphi^{(\max_{i=1}^x\varphi(x)-B)}(x)\]当\(\max_{i=1}^x\varphi(x)-B\leq0\)时\(\varphi^{(\max_{i=1}^x\varphi(x)-B)}(x)=x\)\(1\leqT\leq10^5\),\(1\leqr,B......
  • Solution -「ARC 106E」Medals
    Desc.  Link.  你有\(n\)个朋友,他们会来你家玩,第\(i\)个人\(1...A_i\)天来玩,然后\(A_i+1...2A_i\)天不来,然后\(2A_i+1...3A_i\)又会来,以此类推;  每天你会选一个来玩的人,给他颁个奖,如果没人来玩,你就不颁奖。  你要给每个人都颁\(K\)个奖,问至少需要多少......
  • Window10安装SQL Server
    一、安装SQLServer1、进入官网根据个人所需下载对应版本即可,本文是基于SQLServer2022Express的安装过程2、下载完毕,运行安装指引程序二、安装访问管理工具SSMS1、点击“安装SSMS”按钮,自动跳转到官网下载页,直接点击下载链接即可2、下载完毕运行安装程序3、安装完成,打......
  • P1054 [NOIP2005 提高组] 等价表达式
    P1054[NOIP2005提高组]等价表达式这个题在计算表达式时可能会出现高次方,比如在某一数据中就出现了2^7^10也就是\(2^{70}\)自然溢出会寄,所以要取模自然溢出\(80\)分ullquick_pow(ullx,ullp){ ullres=1; while(p) { if(p&1)res*=x; p>>=1;......
  • 题解 CF1034C【Region Separation】/ SS221116D【Xiong AK 10 IOI】
    很妙的性质题!全是意识流证明见过吗?problem每次选一个非空边集删掉,谓之曰砍树。砍树后需要满足每个连通块的点权和相同。在一个方案中可以砍很多次树,都要满足砍树后的要求。一共有多少种合法方案呢?\(n\leq10^6,1\leqa_i\leq10^9\)。solution假如我们将树砍成\(k\)个连通......
  • CVE-2010-2883 学习记录(漏洞战争,启动!)
    格式分析Header:文件头,用来注明pdf文件版本号Body:主要由组成文件的对象组成,例如图片,文字Cross-regerencetable:交叉引用表,用于存放所有对象的引用、位置偏移、字节长度,用于随机访问pdf中的任意对象Trailer:文件尾,给出交叉引用表的位置(指针)和一些关键对象的信息(指针),......
  • 10.4 国庆 环形dp与基环树笔记
    1.知识点环形dp环形dp的概念•环形dp与基环树在许多环形结构的问题中,我们可以在环中从某个位置把环断开,把这个环变成线性的,然后进行\(dp\)等操作。•把能通过上述操作解决的环形问题称作"可拆解的环形问题"。环形dp的两种策略•第一次在任意位置把环断开成链,按照......
  • 10.1 调试事件读取寄存器
    当读者需要获取到特定进程内的寄存器信息时,则需要在上述代码中进行完善,首先需要编写CREATE_PROCESS_DEBUG_EVENT事件,程序被首次加载进入内存时会被触发此事件,在该事件内首先我们通过lpStartAddress属性获取到当前程序的入口地址,并通过SuspendThread暂停程序的运行,当被暂停后则我没......
  • 每日总结2023/10/03(c#安装教程)
     C#,入门教程(01)——VisualStudio2022免费安装的详细图文与动画教程_visualstudio2022安装c#教程-CSDN博客......
  • stm32f103-2023-10-03
    这是当时在“某知道”上自己的一篇原创回答,由于某些原因目前个人在该平台上的所有回答或隐藏或清空了,现经删整之后收纳回本人博客。======================================================================================问题链接:https://zhidao.baidu.com/question/1604602......