BZOJ 1614架设电话线
最大值最小！？二分
二分答案：
假设需要花费mid元，看是否可以用mid元的花费从1~n。
对于w<mid的，不需免费，0
对于w>mid的，必须免费，1
考虑从1~n可不可以有<k条边权
以以上的原则建立0/1图。
求最短路（最短路是几就包含几个1，且是包含最少1的），if disN<=k 就是可行的
BZOJ1083 繁忙的都市：
https://www.luogu.org/problemnew/show/P2330
最小生成树跑一遍就行；
暴力 O（CMk）显然会炸
如何解决k=1的问题
拉上来：
复制一遍原图，然后连有向边边权为0，跑最短路；
K条边：
复制k遍，从第0层的1，到第k层的w的最短路！？
最后转化为1=> (k-1)*n+n的最短路；
int d（int k，int i）{
return (k-1)*n+i
}
虫洞：负边，小路：正边；
负环=>可以回到过去；
判负环：如果一个点进队次数>=n；有负环；可以回到过去
平均来讲平均进两次队就可以了；每个点进队的次数比较少；
一个小假设，但是可能被卡，假设进队次数>=一个常数，就很可能有负环；
跑两遍单源最短路，分别以A,B为起点，找到一个最小的中间点x，使得dis(A,x)+dis(B,x)最小，其中：
建图：
对每个集合，新建一个节点，将所有集合中的节点向新节点连一条边权为t的边（t为集合内任意两点互达的时间），由新节点向集合中的点连一条边权为0的边；然后↑
直观的感受，按照dfs序操作，一定是最优的；
按照dfs序对宝物排个序，求出相邻两两之间的LCA，然后求最短路，最后还要求最前和最后的最短路；
插入：在 a，b中插入一个c满足a<c<b；
－最短路（a，b）+最短路（a，c）+最短路（b，c）；
Bi,j大的有点过分；
撑死也就300
然后我们是建立了三维立体图
对每一条连边，使之边权为1，然后连一条从底部到最上权值为0的边。
以三点中任意一点为源点，对另两个点求最短路？
下午；
可以让m条边按照g作为第一关键字，s作为第二关键字排序
然后从小到大枚举maxg，把g小于maxg的边放入可用边的集合中
每次枚举后，在可用边中，按照ss排序
用（kruskal）求出最小生成树
可以发现，在前面的枚举中没有用上的边，在后面也不可能被（kruskal）用上，所以可用边最多保留n条
复杂度O(n×m)
然后因为gugugu，所以安利博客：here
题面实际上求的是平面图的最小割；
平面图的最小割等于其对偶图的最短路；
平面图：就是可以摊在二维平面中并且边不交叉；
割：找边集使得把这些点删掉以后源点和终点不连通。
最小割：所有割中，边权之和最小的割；
对偶图：对于每一块平面，把它看做一个点，然后对于对偶图的边，一定会与平面图的边有交点；
那么求出对偶图，跑一个最短路就好了；
鸣谢jyy
求一个环，满足这个环的点权之和/边权之和最大；
把点权看做边权第二维，然后变为有二维的边权，原题变成求一个环，满足边权第二维之和/边权第一维之和最大；
然后二分t，通过看是否有一个环满足上面最后一个式子，如果有，说明答案可行，将t值缩小；
如果没有，说明不可行，将t值增大；
简单来说：
把原图每条边变成Fl-tTl，如果有负环，答案可行，t变小；
最优比例生成树：（因为要写式子，所以gugugu）
显然所有的强连通分量里的钱都可以抢走，把每个强连通求出来，缩成一个点，从点1所在的强连通分量，跑一遍求最长路的SPFA，然后判断是否有酒吧，把有酒吧的取一个max
点数≤100，边数≤1000000（打错了↑）
SOLUTION：
倍增Floyd&Floyd快速幂（懵）
g1[i,j] 从i到j只经过一条边的最短路
g2[i,j] 从i到j只经过一条边的最短路
枚举所有中点k
g2[i,k]=min(g1[i,k]+g1[k,j]);
g2[i,j]=>g4[i,k];
gp[i,j]=min(gp/2[i,k]+gp/2[k,j])；
如何求g19：g3=max(g2[i][k]+g1[k][j]),
g19[i,j]=max(g16[i,k]+g3[k,j])
Dwstroying Road gugugu