题目链接:
https://jzoj.net/senior/#contest/show/2529/2
题目:
题目背景:
尊者神高达很穷,所以他需要跑商来赚钱
题目描述:
基三的地图可以看做 n 个城市,m 条边的无向图,尊者神高达会从任意一个点出发并在起点购买货物,在旅途中任意一点卖出并最终到达终点,尊者神高达的时间很宝贵,所以他不会重复经过同一个城市,但是为了挣钱,他可能会去绕路。当然,由于工作室泛滥,所以一个城市的货物价格可能会发生改变。但是尊者神高达智商不足,他可能在一个很蠢的节点把货物卖掉,所以尊者神高达想知道每一次跑商最多能赔多少钱。
题目大意:
一张无向图,询问两点之间的可能的路径上的最小点权,带修改
前置知识点:广义圆方树
圆方树连边规则:
如果一条边在仙人掌中不属于任何一个环中,那么它直接圆方树中的两个圆点。
对于仙人掌中的任意一个环,则每个环上的点在圆方树上对应的圆点向这个环对应的方点连边。如下图所示
注意圆方树只适用于仙人掌
[JZOJ 5909] [NOIP2018模拟10.16] 跑商(paoshang) 解题报告 (圆方树)
原文:https://www.cnblogs.com/xxzh/p/9800499.html