摘要：
题意： 给你一张无向图，然后有若干组询问，让你输出a->b的最小瓶颈路。 解析： 应该都想过用prime的次小生成树做。。但二维数组开不了那么大。。所以只能用kruskal了。。。。 阅读全文
posted @ 2018-08-03 22:15
WTSRUVF
阅读(223)
评论(0)
推荐(0)
摘要：
自看。。。 借鉴自：https://blog.csdn.net/u011056504/article/details/51222494 1、路径压缩 2、按秩合并 给每个点一个秩，其实就是树高 每次合并的时候都用秩小的指向秩大的，可以保证树高最高为log2(n)log2(n) 操作的时候，一开始所有 阅读全文
posted @ 2018-08-03 20:48
WTSRUVF
阅读(855)
评论(0)
推荐(0)
摘要：
秦始皇统一中国之后要在全国修公路连接各个城市，皇帝只想修成最小生成树（距离最小，不考虑人力），一个道士说自己可以不花人力物力修一条路，经过两方妥协，选择max（两个城市人口/（生成树长度-这条路的长度（连接两个城市的路中，权值最大的那段路）））的路让他变，求这个比值最大值。 阅读全文
posted @ 2018-08-03 19:10
WTSRUVF
阅读(204)
评论(0)
推荐(0)
摘要：
借鉴自：https://chuna2.787528.xyz/hxsyl/p/3290832.html 最小生成树prime算法讲解：https://chuna2.787528.xyz/aiyelinglong/archive/2012/03/26/2418707.html 先用prim求出最小生成树T，在p 阅读全文
posted @ 2018-08-03 17:52
WTSRUVF
阅读(254)
评论(0)
推荐(0)
摘要：
#include #define mem(a, b) memset(a, b, sizeof(a)) using namespace std; const int maxn = 100100, INF = 0x7fffffff; string str; int vis[26]; int main() { cin>> str; mem(vis, 0); int cnt =... 阅读全文
posted @ 2018-08-03 15:09
WTSRUVF
阅读(239)
评论(0)
推荐(0)
摘要：
题意： 给定一个有向图，每条边都有一个权值，每次你可以选择一个结点v和一个整数d，把所有以v为终点的边的权值减小d，把所有以v为起点的边的权值增加d，最后要让所有边权的最小值非负且尽量大 两个特判 1、图中存在负环 则 No Solution （构成差分约束系统的图后bk的最小值为w（u，v）- 1 阅读全文
posted @ 2018-08-03 10:18
WTSRUVF
阅读(297)
评论(0)
推荐(0)
摘要：
在判断环路时，如果没有源点，则建立超级源s，从s出发与所有其它点相连，权值为0。 那么从s出发进行spfa就相当于把所有的点加入队列中，且标记，且d[i] = 0; 阅读全文
posted @ 2018-08-03 08:54
WTSRUVF
阅读(210)
评论(0)
推荐(0)
浙公网安备 33010602011771号