或者跑一个dp
dp[i]表示总花费不超过i的情况下的最短路
dij套dp
o(nk)个点
对于每一个点u，建立k+1个点表示到点u花费费用为i
比如u-->v长度为c
u,0-->v,c
u,1-->v,c+1
二分答案mid
只能通过限重>=mid的边
把这些边都加进去
判断1和n联通
dijkstra
if(dis[v]<min(dis[u],w)) dis=min(dis[u],w)
kruscal
其实就是找到一棵最大生成树
贪心思想每一次加上最大的边
如果联通就换下一条边
这不就是kruscal吗？
当第一次使1，n联通的时候，这一次加的边就是答案
把优惠条件看成一种边
u-->v长度为w
从某一个点出发走到1就是一种方案
希望走最短路
反向建边跑1到其它点的最短路
枚举区间，然后跑dij
但是m可能很大，怎么办？
发现n很小，只有100
所以我们只需要以每一个真实存在的地位作为端点就好了 枚举量o(n)
STL优先队列怎么合并
启发式合并
合并ab，看看a和b分别多大
把点比较少的堆拆掉，一个个合并到另一个堆
每一个点至多产生logn次合并代价
O(nlognlogn)
独立集：具有遗传性和交换性
x1a+x2b+x3c=0
生成森林：选出一些边集构成森林
dfs序上限是2n（点数+边数）
找到出现的最晚a和最早b，在这个区间内一定出现过他们的lca
找到高度最小的点就是他们的lca
o(nlogn)预处理，O(1)查询
每个点一定属于一个重链
重链条数和轻边边数是logn级别
证明和启发式合并差不多
原文：https://www.cnblogs.com/lcezych/p/11331247.html