2017年“嘉杰信息杯” 中国大学生程序设计竞赛全国邀请赛:H—Highway_yuanS7的博客-程序员信息网

技术标签: 动态规划  dp  

题目链接:http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1267

Highway

In ICPCCamp there were  n  towns conveniently numbered with  1,2,,n  connected with  (n1)  roads. The  i -th road connecting towns  ai  and  bi  has length  ci . It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build  (n1)  highways so that any two towns reach each using only highways. Building a highway between towns  x  and  y  costs him  δ(x,y)  cents, where  δ(x,y)  is the length of the shortest path between towns  x  and  y  using roads.

As Bobo is rich, he would like to find the most expensive way to build the  (n1)  highways.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer  n . The  i -th of the following  (n1)  lines contains three integers  ai bi  and  ci .

  • 1n105
  • 1ai,bin
  • 1ci108
  • The number of test cases does not exceed  10 .

Output

For each test case, output an integer which denotes the result.

Sample Input

5
1 2 2
1 3 1
2 4 2
3 5 1
5
1 2 2
1 4 1
3 4 1
4 5 2

Sample Output

19
15

题目大意:给你一颗已知的树,求出新建的一颗权值最大的树的权值

解题思路:树形dp,求出每个点到树其他点的最长距离再减去树中的最长路径。

将每个点的最长路径添加到新建的树中,除了树中最长的那条路径会重复一次(构成一个环),不会形成其他环,而所有的点都添加到了新建的树中,于是构成了一颗权值最大的树。

dp[u][0]:u到子树节点的最长距离,dp[u][1]:u到子树节点外其他节点的最长距离

dp[u][0]很容易在dfs中计算出来。


dp[v][1]:若v不是u子树最长路径经过的点,dp[v][1] = max( dp[u][1]+Luv , dp[u][0]+Luv )

             若v是u子树最长路径所经过的点,dp[v][1] = max( dp[u][1]+Luv , dp[u][0]+Se[u])

Se[u]带表u的子树中第二长的路径长度。

#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <iostream>  
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;  
typedef  __int64 ll;
const int N = 100100;
const int M = 20;
const int INF = 0x3fffffff;

struct  Edge
{
	int node,len;
	Edge*next;
}m_edge[N*2];
int Ecnt;
Edge*head[N];
int vis[N],flag[N];  
ll dp[N][2],second[N];
//dp[u][0]:u到子树节点的最长距离,dp[u][1]:u到子树节点外其他节点的最长距离
//second[u]:子树节点到u的第二长路径,flag[v]:节点v的上层节点的最长路径是否经过v

void init()
{
	Ecnt = 0;
	fill( head , head+N , (Edge*)0 );
	fill( flag , flag+N , 0 );
	fill( second , second+N , 0 );
}

void mkEdge( int a , int b , int c )
{
	m_edge[Ecnt].node = a;
	m_edge[Ecnt].len = c;
	m_edge[Ecnt].next = head[b];
	head[b] = m_edge+Ecnt++;

	m_edge[Ecnt].node = b;
	m_edge[Ecnt].len = c;
	m_edge[Ecnt].next = head[a];
	head[a] = m_edge+Ecnt++;
}

ll dfs1( int u )
{
	vis[u] = true; dp[u][0] = 0;
	for( Edge*p = head[u] ; p ; p = p->next ){
		int v = p->node;
		if( !vis[v] ){
			ll w = dfs1( v );
			dp[u][0] = max( dp[u][0] , w+p->len );
		}
	}
	return dp[u][0];
}

void dfs2( int u  )
{
	vis[u] = true;
	int fg = 0;
	for( Edge*p = head[u] ; p ; p = p ->next ){
		int v = p->node;
		if( !vis[v] ){
			if( !fg && dp[u][0] == dp[v][0]+p->len ) { flag[v] = 1;fg = 1; }
			else second[u] = max( second[u] , dp[v][0]+p->len );
			dfs2( v );
		}
	}
}

void dfs3( int u )
{
	vis[u] = true;
	for( Edge*p = head[u] ; p ; p = p->next ){
		int v = p->node;
		if( !vis[v] ){
			if( !flag[v] ) dp[v][1] = max( dp[u][1]+p->len , dp[u][0]+p->len );
			else dp[v][1] = max( dp[u][1]+p->len , second[u]+p->len );
			dfs3( v );
		}
	}
}

int main()
{
	int n,a,b,c;
	while( ~scanf("%d",&n) ){
		init();
		for( int i = 0 ; i < n-1 ; ++i ){
			scanf("%d%d%d",&a,&b,&c);
			mkEdge( a , b , c );
		}
		memset( vis , 0 , sizeof(vis) );
		dfs1( 1 );
		memset( vis , 0 , sizeof(vis) );
		dfs2( 1 );
		memset( vis , 0 , sizeof(vis) );
		dfs3( 1 );
		ll rec = 0,ans = 0;
		for( int i = 1 ; i <= n ; ++i ){
			ll t = max( dp[i][0] , dp[i][1] );
			ans += t;
			rec = max( rec , t );
		}
		ans -= rec;
		printf("%I64d\n",ans);
	}
	return 0;
}



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jiangzhiyuan123/article/details/72253731

智能推荐

计算机室内设计 cad 论文,cad室内设计开题报告_思睿-three的博客-程序员信息网

cad室内设计开题报告简介:此栏目是开题报告和室内设计有关的论文例文,免费给你写cad室内设计柜子提供有关参考文献。一、研究背景1 基于英语新课程标准的要求。《英语课程标准》指出:必须正视学生外语学习基础和发展要求的差异,遵循外语学习的客观规律,英语教学强调。摘 要:对于博物馆而言,其是对一个地区城市乃至一个国家的历史文化的保留和发展,通过建筑空间向社会大众表现。 博物馆的内在的建筑空间格局对其展...

ADAS技术概要_linolzhang的博客-程序员信息网

先进驾驶辅助系统(Advanced DriverAssistant System),简称ADAS,是智能交通领域的一个大方向,近几年ADAS迅速发展,在车道线检测、前车防撞、疲劳驾驶、紧急壁障、信号灯识别等方面都取得了长足的进步,这也是我们把ADAS单独作为一节来进行阐述的原因。        当然ADAS系统会用到多种传感器,比如激光雷达、深度摄像头等,这里我们仅通过传统的RGB摄像头来

Java中解析日志_碧海凌云的博客-程序员信息网_java 日志解析

Java中解析日志常用的是Grok,Grok是一个用于解析logs和其它文件的简单易用的API,并且它可以将这些无结构的logs转换成结构化的数据(JSON),使用正则表达式对logs进行解析,常用的是grok和java-grok,下面来具体说说各自的使用grokgrok是io.thekraken组织提供的实现,在mven仓库中输入io.thekraken就可以找到对应的jar包简单Java项目如果是简单Java项目,直接引入依赖的jar包即可,对于0.1.5的版本,必须引入5个jar包:comm

科研文献管理 Zotero +科研笔记 Obsidian_Kasen's experience的博客-程序员信息网

这里写自定义目录标题前言软件安装Obsidian 插件我使用的插件ZoteroQuickLookZotFileBetter BibTex for Zotero配置Mdnote for Zotero配置取消自动给author 添加 tag后续前言此前,一直使用 国产 NoteExpress 文献管理软件 + Word 写作 + OneNote 笔记。 NoteExpress 对中文支持好,本地文件存储可以以和NoteExpress题录中的目录树一样的形式存在。这种方式很方便直接查找本地文件,也适合将这些文

深度学习入门一阶段demo练习:利用深度学习框架,搭建自定义卷积神经网络,在本地的imageNet数据集上实现图像分类,要求准确率达到70%以上。(注:本任务主要练习本地数据集的读取)_CV干饭王的博客-程序员信息网

深度学习入门一阶段demo练习:demo任务:利用深度学习框架(TensorFlow2.0及以上版本、pytorch1.0及以上版本),搭建自定义卷积神经网络,在本地下载好的imageNet数据集上实现图像分类,要求准确率达到70%以上。(注:本任务主要练习本地数据集的读取。)本次图像分类选用mini-imagenet数据集,图片类别为:n01558993xxxxxxxxn03417042xxxxxxxxn02089867xxxxxxxxn02129165xxxxxxxxn0451500.

随便推点

发现宝藏!这个小网站,包含了200+的优质谷歌插件,你值得拥有_代码讲故事的博客-程序员信息网_插件宝藏网站

发现宝藏!这个小网站,包含了200+的优质谷歌插件,你值得拥有。没有插件的Chrome ,就像手机没有安装APP,没有什么用。但是安装了插件的Chrome就不一样了,几乎能满足我们现阶段的所有需求!比如免费看V1P视频:屏蔽页面所有广告:一键提取页面所有图片,并实现下载:那么,问题来了,在我们根本不知道有什么插件的情况下,怎么才能找到并下载想要的插件呢?今天,给大家推荐一个网站–极简插件,一个Chrome浏览器扩展插件的搬运工,包含200多个实用插件。那么这个网站到底是什么样的呢?让我们来一探究竟

Linux服务 Nginx(一)_dingcong4061的博客-程序员信息网

Linux服务 Nginx(一) Nginx是一款轻量级的Web服务器/反向代理服务器及电子邮件(IMAP/POP3)代理服务器,并在一个BSD-like 协议下发行.其特点是占有内存少,并发能力强,事实上nginx的并发能力确实在同类型的网页服务器中表现较好,中国大陆使用nginx网站用户有:百度、京东、新浪、网易、腾讯、淘宝等. http协议...

C语言 VS2019编译器实现简易井字棋小游戏~_yzxss的博客-程序员信息网_vs2019制作游戏

运用C语言制作简易井字棋小游戏制作教程 适合编程萌新练习的小项目~

适当的Java堆大小的5个技巧_dnc8371的博客-程序员信息网

确定生产系统合适的Java堆大小不是一件容易的事。 在我的Java EE企业经验中,我发现由于Java堆容量和调整不足而导致的多个性能问题。 本文将为您提供5个技巧,这些技巧可以帮助您确定当前或新生产环境的最佳Java堆大小。 这些技巧中的一些对于预防和解决java.lang.OutOfMemoryError问题也非常有用。 包括内存泄漏。 请注意,这些技巧旨在“帮助您”确定适当的Ja...

Java AES加密案例_diaomu5377的博客-程序员信息网

AES加密原理http://www.blogjava.net/amigoxie/archive/2014/07/06/415503.htmlPHP 加密https://segmentfault.com/a/1190000002798716Java AES接口详解http://blog.zheezes.com/java-aes-encryption-uses-and-p...

lisp填挖横断面提取_如何在别人提供的cad横断面设计图中提取横断面地面线数据..._weixin_39903176的博客-程序员信息网

(defun c:test()(setq desktop (strcat (lt:sys-deskTopDir) "\\坐标导出.txt"))(setq ff (open desktop "w"))(setq b (getreal "\n请输入纵向比例尺.&lt;200&gt;:"))(setq c (getreal "\n请输入横向比例尺.&lt;200&gt;:"))(if (not b) (...

推荐文章

热门文章

相关标签