首页 > 其他 > 详细

[JZOJ 5909] [NOIP2018模拟10.16] 跑商(paoshang) 解题报告 (圆方树)

时间:2018-10-16 21:11:04      阅读:166      评论:0      收藏:0      [点我收藏+]

题目链接:

https://jzoj.net/senior/#contest/show/2529/2

题目:

题目背景:
尊者神高达很穷,所以他需要跑商来赚钱
题目描述:
基三的地图可以看做 n 个城市,m 条边的无向图,尊者神高达会从任意一个点出发并在起点购买货物,在旅途中任意一点卖出并最终到达终点,尊者神高达的时间很宝贵,所以他不会重复经过同一个城市,但是为了挣钱,他可能会去绕路。当然,由于工作室泛滥,所以一个城市的货物价格可能会发生改变。但是尊者神高达智商不足,他可能在一个很蠢的节点把货物卖掉,所以尊者神高达想知道每一次跑商最多能赔多少钱。

题目大意:

一张无向图,询问两点之间的可能的路径上的最小点权,带修改

前置知识点:广义圆方树

圆方树连边规则:

如果一条边在仙人掌中不属于任何一个环中,那么它直接圆方树中的两个圆点。

对于仙人掌中的任意一个环,则每个环上的点在圆方树上对应的圆点向这个环对应的方点连边。如下图所示

注意圆方树只适用于仙人掌

技术分享图片

 

[JZOJ 5909] [NOIP2018模拟10.16] 跑商(paoshang) 解题报告 (圆方树)

原文:https://www.cnblogs.com/xxzh/p/9800499.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!