题面 这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了. [collapse title="展开代码"] #include<cstdio> #include<cs…

题面 标题比题面好懂系列. 题目就是要求所有环中边权之和与环长之比的最小值. 令点权为1(方便统计长度. 更一般的0/1分数规划题中点权是可以任意取的, 后续推导一致), 则 $ ans=\sum{e.w}/\sum{v.w}$ $ \sum{e.w}-ans*\sum{v.w}=0$ $ \sum(e.w-ans*v.w)=0$ $ \sum_{…

这道题要求最大收费点的最小值,明显是二分答案 二分check(maxf)函数目标:判断能否在 最大收费点小于maxf 的条件下,走到终点 能则缩小maxf, 否则只能是更大的maxf 具体实现: dijkstra松弛的时候加个判断 点权小于maxf 就行了 [collapse title="展开代码"] #include<cstdio>…

题面 tarjan缩点模板题 tj的思路: 强连通分量可以相互到达, 必定在一个环上, 一次dfs找出所有尽量大的环即可. sta里面是表示当前所有可能能构成强连通分量的点, 追溯值low[x]表示点x及其子孙节点连的所有点中dfn的最小值, 如果遇到环就会发现不能再往下搜, 接着会一直回溯至进入环的点x(low[x]=dfn[x], 途中要从后往…

规律：对于自然数n，若n为偶数，则n^1=n+1；若n为奇数，则n^1=n-1 因此 0与1 2与3 4与5 ……^1可构成成对变换 应用：邻接表存图，把每条边及其反向边放在从2开始的连续位置，则有 若e[i].t为边i的终点，则其反向边为i^1，其起点为e[i^1].t。