标签:图

OI

[POJ3268]Silver Cow Party[SPFA]

cgazn阅读(136)评论(0)赞(0)

题面 这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了.

OI

[HNOI2009]最小圈[0/1分数规划,SPFA]

cgazn阅读(198)评论(0)赞(0)

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

OI

[洛谷P1462]通往奥格瑞玛的道路[二分答案]

cgazn阅读(82)评论(0)赞(0)

这道题要求最大收费点的最小值,明显是二分答案 二分check(maxf)函数目标:判断能否在 最大收费点小于maxf 的条件下,走到终点 能则缩小maxf, 否则只能是更大的maxf 具体实现: dijkstra松弛的时候加个判断 点权小于...

OI

[洛谷P1262]间谍网络[tarjan缩点]

cgazn阅读(118)评论(0)赞(0)

题面 tarjan缩点模板题 tj的思路: 强连通分量可以相互到达, 必定在一个环上, 一次dfs找出所有尽量大的环即可. sta里面是表示当前所有可能能构成强连通分量的点, 追溯值low[x]表示点x及其子孙节点连的所有点中dfn的最小值...

OI

异或运算实现成对变换

cgazn阅读(126)评论(0)赞(0)

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