Travelling

题意不多赘述。 注：全文所用的“点 \(u\) 的出度”均指的是点 \(u\) 在原图上的出度。 首先我们考虑 \(r_{i} = 0\) 的情况怎么写，这时我们会发现要么答案是 \(0\) 要么无解。当当前点 \(u\) 无论怎么走都走不到一个环上，即无论怎么走最终都会走到一个出度为 \(0\) ......

题意 给定一张图，走出当前边的时间为 \(i\)。 \(q\) 次询问，问 \(s\) 是否能在 \(l \to r\) 中走到 \(t\)。 Sol 考虑将边从大到小插入图中。 注意到当前边只能对起点造成贡献。 复杂度 \(O(n \times \max\{n, m\})\) Code #incl ......

首先将边反向，再按 \(r\) 从大到小排序，这样可以使得答案的转移没有后效性。 令 \(ans_i\) 表示 \(i\) 这个点最少有多少资产方能无限地走下去。（初值为 \(inf\) ） 依次枚举每一条边。（令 \(u\) 为这条边的起点，\(v\) 为这条边的终点） 首先对现在的图进行一遍 t ......

Fox And Travelling 题面翻译 给定一张 \(n\) 个点 \(m\) 条边的无向图。 一个点只有当与它直接相连的点中最多只有一个点未被选择过时才可被选择。 询问对于每个 \(k \in [0,n]\)，有序选择 \(k\) 个点的方案数。 \(n \le 100\)，\(m \le ......

prologue 模拟赛的一道题，结果没做出来，丢大人，败大兴。所以过来糊一篇题解。 analysis 我们看到数据范围这么大，那么肯定不可以一个一个遍历（废话），所以就要考虑这个题目的性质。 我们先假设，极端数据 \(2 ^ {1000} - 1\)，这个数字中包含了 \(999\) 个 1（正好 ......

# 题目大意 给出一个有向图，每条边有两个权值，分别代表通过该路径的最小要求 $r_i$，和通过后增加的值 $p_i$。问：从每个点出发，各需要至少多少初始值，才能不停走下去。 # 思路 首先，分析一下，如果设 $f_i$ 为从 $i$ 点出发需要的最少初始值。那么可以轻易的推出转移方程：$f_i= ......

UVA10702 Travelling Salesman 题解 题面： 有个旅行的商人，他每到一个的新城市，便卖掉所有东西再购买新东西，从而获得利润。从某城市 A 到某城市 B 有固定利润（B 到 A 的利润可能不同）。已知城市可以重复到达，从 S 点出发，经过 T 个城市，有 E 个城市能作为终点 ......

计数好题。 首先对于每个连通块独立考虑，最后合并答案。 发现 点数超过 1 的强连通分量一定删不掉。 - 若连通块中存在 点数超过 1 的强连通分量 - tarjan 缩点之后，称这些点数超过 1 的强连通分量为关键点； - 那么两关键点之间的点也不能删； - 于是对于剩下的点直接 dp 即可，由于 ......