jzoj 5905.【NOIP2018模拟10.15】黑暗之魂(darksoul) 基环树+_Amber_lylovely的博客-程序员宅基地

技术标签:   DP  

Description

oi_juruo热爱一款名叫黑暗之魂的游戏。在这个游戏中玩家要操纵一名有 点生命值的无火的余灰在一张地图中探险。地图中有n个篝火(也就是存档点)。在篝火处休息可以将生命值恢复满。每个篝火都会向其他篝火的其中之一连有一条通道(显然,通道是双向的),这些篝火之间都相互可达。也就是说,这是一张n个点,n条边的无向连通图。每条通道里都有一些怪物,经过oi_juruo的分析,他得到了每条边的怪物会对他造成的伤害值 .为了向oier们表演他高超的游戏技巧,他要从任意一个篝火跑到任意另一个篝火而不在之间的篝火休息,在此期间,他会和他经过的通道中的怪物战斗并损失 的生命值。现在oi_juruo想知道,他的生命值 至少为多少,才能完成任意一条旅途。oi_juruo并不傻,他会走最安全的路。本题时限为3000ms

Input

第一行一个整数n。之后n行,每行三个整数ui,vi,ai ,表示有一条从ui 连向vi ,怪物伤害值为ai 的通道。

Output

一行一个数hp,表示无火的余灰的最小生命值。

Sample Input

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

Sample Output

8

样例说明
从2到5的路最危险,2 1 4 5受到了7点伤害,所以需要有8点生命值。

Data Constraint
在这里插入图片描述

分析:
题目求一个有 n n n个点和 n n n条边的图的最短路的最大值。
显然这个图可以看做是一个环+很多子树。
我们先用连通分量把这个环拿出来。
显然最短路有可能在子树里,设 f [ i ] f[i] f[i]为以 i i i开始的最长链,我们遍历这些子树并维护 f f f值,对于子树中的一点,经过该点的最长链就是最大值+次大值。
对于环上的某个点 x x x,可以延伸 f [ x ] f[x] f[x]的长度。考虑经过环的路径。因为 x x x y y y y y y x x x是一样的,我们可以强制环上顺时针。然后在环内搞一个环的长度的前缀和,那么以 y y y为结尾的路径最长为 f [ x ] + f [ y ] + ( s [ y ] − s [ x ] ) f[x]+f[y]+(s[y]-s[x]) f[x]+f[y]+(s[y]s[x])。然后单调队列优化一下即可。

代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define LL long long

const int maxn=1e6+7;

using namespace std;

int n,cnt,cir,bcnt,tot,mid,head,tail,flag;
int ls[maxn],dfn[maxn],low[maxn],belong[maxn];
bool vis[maxn];
int id[maxn],q[maxn*2];
LL ans,f[maxn*2],size[maxn*2],s[maxn*2],dis[maxn*2],sumdis;

struct edge{
	int y,w,next;
}g[maxn*2];

struct node{
	int x,y,w;
}a[maxn];

vector <int> sta;

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void add(int x,int y,int w)
{
	g[++cnt]=(edge){y,w,ls[x]};
	ls[x]=cnt;
}

void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++cnt;
    vis[x]=1; sta.push_back(x);
    for (int i=ls[x];i>0;i=g[i].next)
    {
        int y=g[i].y;
        if (y==fa) continue;
        if (!dfn[y])
        {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
        }
        else
        {
            if (vis[y]) low[x]=min(low[x],dfn[y]);
        }
    }
    if (low[x]==dfn[x])
    {
        bcnt++;
        int y=0,flag=0;
        if (sta.back()!=x) flag=1,cir=bcnt;
        while (y!=x)
        {
            y=sta.back();
            sta.pop_back();
            belong[y]=bcnt;
            vis[y]=0;
            if (flag) id[++tot]=y;
        }
    }
}

void dfs(int x,int fa)
{
	LL max1=0,max2=0;
	for (int i=ls[x];i>0;i=g[i].next)
	{
		int y=g[i].y;
		if ((belong[y]==cir) || (y==fa)) continue;
		dfs(y,x);
		LL d=f[y]+g[i].w;
		if (d>max1)
		{
			max2=max1;
			max1=d;
		}
		else if (d>max2) max2=d;
	}
	ans=max(ans,max1+max2);
	f[x]=max1;
}

bool cmp(node a,node b)
{
	if (a.x==b.x)
	{
		if (a.y==b.y) return a.w<b.w;
		return a.y<b.y;
	}
	return a.x<b.x;
}

int main()
{
	freopen("darksoul.in","r",stdin);
	freopen("darksoul.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++)
	{
		a[i].x=read(),a[i].y=read(),a[i].w=read();
		if (a[i].x>a[i].y) swap(a[i].x,a[i].y);
	}
    sort(a+1,a+n+1,cmp);   
    for (int i=1;i<=n;i++)
    {
    	if (a[i].x==a[i].y) flag=1;
    	else
    	{
    		if ((a[i].x==a[i-1].x) && (a[i].y==a[i-1].y)) flag=1;
    		else
    		{
    			add(a[i].x,a[i].y,a[i].w);
    			add(a[i].y,a[i].x,a[i].w);
    		}
    	}
    }       
    if (flag)
    {
    	cir=1;
    	dfs(1,0);
    	printf("%lld",ans+1);
    	return 0;
    }
	tarjan(1,0);
	for (int i=1;i<=tot;i++) dfs(id[i],0),size[i]=f[id[i]];	
	for (int i=1;i<=tot;i++)
	{
		int d;
		if (i==1) d=id[tot];
		     else d=id[i-1];
		for (int j=ls[id[i]];j>0;j=g[j].next)
		{
			if (g[j].y==d)
			{
				dis[i]=(LL)g[j].w;
				break;
			}
		}
	}	
	for (int i=tot+1;i<=2*tot;i++) dis[i]=dis[i-tot],size[i]=size[i-tot];
	for (int i=1;i<=2*tot;i++) s[i]=s[i-1]+dis[i];
	sumdis=s[tot];
	head=tail=1;
	q[head]=1;	
	for (int i=2;i<=2*tot;i++)
	{
		while ((head<=tail) && (s[i]-s[q[head]]>sumdis/2)) head++;
		if (head<=tail) ans=max(ans,size[i]+s[i]+size[q[head]]-s[q[head]]);
		while ((head<=tail) && (size[q[tail]]-s[q[tail]]<=size[i]-s[i])) tail--;
		q[++tail]=i;
	}	
	printf("%lld",ans+1);	
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liangzihao1/article/details/83067513

智能推荐

java使用极光推送_java利用极光推送进行推送的代码_鹊华清扬的博客-程序员宅基地

今天学了推送的相关知识,记录下,以免忘记1.所有平台PushPayload payload = PushPayload payload = PushPayload.newBuilder().setPlatform(Platform.all()).setAudience(Audience.alias("alias")).setNotification(Notification.alert("测试推送...

学员感言html效果图,学员感言丨非计算机专业学员 开始学HTML5的点点滴滴_weixin_39599372的博客-程序员宅基地

学员感言丨非计算机专业学员 开始学HTML5的点点滴滴来源:奇酷教育 发表于:2017-08-03 12:09:25在奇酷学员学习HTML5的这段时间里,让我学习到了实用的技能和知识。我是一个非计算机类学生,可以说是对编程一窍不通,在选择HTML5培训之前,我逃避过、犹豫过、迷茫过,站在人生的十字路口,不知道该何去何从。其实编程对于初学者的难度还是很大的,因为HTML5手机应用的最大优势就是...

junit报assertexception_JUnit中测试异常抛出的方法_妞妞脾气灰常大的博客-程序员宅基地

最近在做TWU关于TDD的作业,对JUnit中测试异常抛出的方法进行了一些学习和思考。在进行单元测试的时候有的时候需要测试某一方法是否抛出了正确的异常。例如,我有一个方法,里面对一个List进行读取操作,可能会抛出IndexOutOfBoundsException,我希望在单元测试中通过测试保证该方法会正确的抛出正确类型的异常。总结起来这样的测试异常是否被正确抛出的方法有三种:1. try…fai...

tl494组成的超声波发射电路_透彻分析利用TL494组成的逆变器电路_weixin_39796238的博客-程序员宅基地

现在利用TL494组成400W大功率稳压逆变器电路,它的激式变换部分是采用TL494和VT1、VT2、VD3、VD4一起构成灌电流驱动电路,驱动两路各配两只60V/30A的MOSFET开关管。需提高输出功率时,每路可采用3~4只开关管并联使用,整体电路也不变。TL494在逆变器中的应用方法如下:本文引用地址:http://www.eepw.com.cn/article/201612/327693....

Node.JS+Vue+Vite+D3可视化_追风筝的人i的博客-程序员宅基地_node vite

Node.JS+Vue+Vite+D3可视化——mac从 Vite 与 Vue 开始的 D3 数据可视化之旅(MAC)准备些啥呢?前期工作Node.jsyarngitVite站Vue+D3可视化安装d3依赖安装axios从 Vite 与 Vue 开始的 D3 数据可视化之旅(MAC)本文章用于入门学习Vue和Vite的搭建,同时使用D3实现数据可视化。准备些啥呢?首先准备好我们旅行的行李清单Node.js ,因为mac自带,所以我就直接使用的自带;npm or yarn:包管理工具,这里我使用

凯恩帝绝对坐标清零_凯恩帝 K90T i 数控车床系统使用手册分享_Oliverzzzhang的博客-程序员宅基地

A)机床实际运动方法1、可调整进给倍率2、采用单程序段,即是每按一次启动键后刀具走一个动作(执行一个程序段)后停止,再按启动键后刀具走下一个动作后(执行下一个程序段)停止,这样可以检查程序。B)机床不动, 观察显示位置变化或通过图形功能, 观察加工时的刀具轨道的变化。1.5. 数据的显示和设定:(1) 刀具补偿的显示和设定方法。(2) 参数的显示和设定。(3) 用诊断参数判断机床的输入输出口信号状...

随便推点

回归之一多目标跟踪算法评价指标_weixin_34368949的博客-程序员宅基地

实习生像条狗,去年开始实习到现在都没有更新自己的博客,痛定思痛,决定回归,正好课题是目标跟踪这块,先就多目标跟踪算法评价指标谈谈自己的观点:单目标跟踪算法的评价指标不用我多说,因为其跟踪情况较为简单,已经有较为明确的判断指标,但是一直以来,多目标跟踪的评价指标都未统一,跟踪算法的论文中也是用各种评价指标来分析自身的算法,但是缺少与其它算法的横向比较,孰优孰劣不得而知。因为自己的毕业课题设计到这...

du和df_我什么都布吉岛的博客-程序员宅基地

df(disk free) 是一个非常棒的命令,将会告诉你在所有已挂载的磁盘的磁盘大小、空间。附带的-h选项让这个大小更加符合人类阅读。du(disk usage)最适合用在需要查看目录和子目录大小的场合。-sh选项是他们的常用搭配,-s(summarize)汇总,-h(human-readable)人类可读的。df du的区别,df命令提供了一个全面的数据,用于说明整个文件系统上使用了多少空间。 du命令是给定目录或子目录的更准确的快照。https://www.redhat.com/sysadmi

crontab凌晨一点备份mysql_利用crontab每天定时备份MySQL数据库_weixin_39588084的博客-程序员宅基地

当数据库服务器建立并正式投入生产使用后,我们不得不担忧一个问题:当数据库遭到破坏后,怎样安然恢复到最后一次正常的状态,使得数据的损失达到最小。我这里以本博客的wordpress数据为例,来讨论并实现全自动话的数据备份。一、配置备份任务1、建立自动备份脚本为了使数据库备份和恢复的符合我们的实际要求(备份保留七天,每天凌晨备份一次),用一段符合要求的Shell脚本来实现整个备份过程的自动化。[root...

我刚刚发表的文章_佛山永坤电机的博客-程序员宅基地

我刚刚发表的文章:2016年初计划实现了多少?那去了?奇了怪了

thinphp 生成带头像的小程序码_weixin_30340353的博客-程序员宅基地

  //获得二维码 public function qrcode() { header('content-type:text/html;charset=utf-8'); //配置APPID、APPSECRET $id=$_GET['uid']; $APPID = C('WX_APPID');...

推荐文章

热门文章

相关标签