7831
P7831 [CCO2021] Travelling Merchant
题意不多赘述。 注:全文所用的“点 \(u\) 的出度”均指的是点 \(u\) 在原图上的出度。 首先我们考虑 \(r_{i} = 0\) 的情况怎么写,这时我们会发现要么答案是 \(0\) 要么无解。当当前点 \(u\) 无论怎么走都走不到一个环上,即无论怎么走最终都会走到一个出度为 \(0\) ......
P7831 [CCO2021] Travelling Merchant CWOI1113B
首先将边反向,再按 \(r\) 从大到小排序,这样可以使得答案的转移没有后效性。 令 \(ans_i\) 表示 \(i\) 这个点最少有多少资产方能无限地走下去。(初值为 \(inf\) ) 依次枚举每一条边。(令 \(u\) 为这条边的起点,\(v\) 为这条边的终点) 首先对现在的图进行一遍 t ......
P7831 [CCO2021] Travelling Merchant
# 题目大意 给出一个有向图,每条边有两个权值,分别代表通过该路径的最小要求 $r_i$,和通过后增加的值 $p_i$。问:从每个点出发,各需要至少多少初始值,才能不停走下去。 # 思路 首先,分析一下,如果设 $f_i$ 为从 $i$ 点出发需要的最少初始值。那么可以轻易的推出转移方程:$f_i= ......