考前图论速成，启动！
一天怎么可能复习的完啊
图论烂完了
考前图论速成，启动！
最短路
通信线路
SOL1：分层图
如果题目中DP有后效性，用SPFA(dij也可以吗，不过这个应该是个DP，dij的贪心思想是不可以的吧）。而这是一个图，显然有。
dis对应表示的是当前走过的边中最大的边
- 对应层数需要注意，这里k条免费，故有k+1层
- 更优雅的写法直接用二维数组，不需要以为计算了。
SOL2：二分答案
二分答案，将边权转化为0/1，对应跑dij即可
- 注意全部免费的情况答案为0
最优贸易
发现答案就是
对应建正反图，取点权max/min，这不符合贪心，用spfa
(!((opt == 0) ^ (dis[opt][v] > w)) && dis[opt][v] != w)
对于这种类似于DP的状态转移，都可以使用分层图思想，表示我当前的状态转移（以前的我已经不是现在的我了）
道路与航线
发现双向边无负权，单向边不成环。对应将双向边看成整体，类似于缩点，里面跑dij。对应单向边就构成了有向无环图。拓扑即可。
没有必要担心拓扑只从入度为0的点开始，而这之中没有s。因为s一定是入度为0的点，如果不是，则给予s入度的连通块一定到不了
每到达一个连通块，我们可以把所有点都先放入优先队列中。因为有些点是通过其他连通块更新过的，有些没有，这样可以自动找到从那个地方开始。
- 注意判定不可达的标准
通往奥格瑞玛的道路
二分答案费用。dij一下判断到达是血量有没有清空
最短路只需要判断自环，不需要判断重边
最小生成树
走廊泼水节
保证最小生成树不变就是要加的权值比属于最小生成树的边的权值大1
不需要全局最大值，只是当前的链接边的值大1即可
沙漠之王
0/1分数规划。如果结果>0，l = mid。否则r = mid。判断用prim即可
注意二分区间大小和循环次数，卡这个差不多得了
负权
观光奶牛
0/1分数规划
- 单项边去双向边了
Tarjan-DCC
网络
缩点后发现每一次操作都会减少答案数量，对应操作二端点可以向上跳，条到另外一个e-DCC后表示少一个桥，修改答案。
这个过程可以用并查集维护。相当于将跳的过程中的一群点当成一个并查集，整体维护他们的信息
注意跳的时候顺序维护。先设置fa，在find跳转
Tarjan
缩点
- 有向图建无向边……