/目录1问题描述2解决方案2.1构造最小生成树示例2.2伪码及时间效率分析2.3具体编码（最佳时间效率）  何为Kruskal算法？该算法功能：求取加权连通图的最小生成树。假设加权连通图有n个顶点，那么其最小生成树有且仅有n-1条边。该算法核心思想：从给定加权连通图中，选择当前未被选择的，不能形成回...

                          &nbs...

TruckHistoryTimeLimit:2000MS MemoryLimit:65536KTotalSubmissions:19860 Accepted:7673DescriptionAdvancedCargoMovement,Ltd.usestrucksofdifferenttypes.Som...

题目：SlimSpanUVA1395题意：给出一副无向有权图，求生成树中最小的苗条度（最大权值减最小权值），如果不能生成树，就输出-1；思路：将所有的边按权值有小到大排序，然后枚举每一条边，以这条边开始利用Kruskal算法生成树，生成过程中求出权值的最大值，这个最大值减去当前枚举的边的权值就是苗条度，再动态维护一下最...

　　平面上有n个点，现在把他们划分成k个部分，求不同部分之间最近距离的最大值。　　两个部分的距离就是两个部分中的最近的点对的距离。 　　n<=1000 　　我们把所有的点全部建边。　　然后我们要更新答案，就要尽量弄掉短的边。　　于是就按照kruscal那样从短的开始弄。　　当然要用并查集。　　...

 　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。　　答案对于31011取模。 　　先考虑错误的prim——　　这个是我的第一感，拿到题目，...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ407.html套路啊。先按照两个节点顺序各搞一个kruskal重构树，然后问题转化成两棵kruskal重构树，不断询问，每次询问让你判断是否有点同时存在于第一棵树的一个子树和第二棵树的一个子树中。这个东西就转成dfs序之后主席...

原文链接https://www.cnblogs.com/zhouzhendong/p/NOI2018Day1T1.html 　　给定一个无向连通图，有$n$个点$m$条边，每条边有两个属性：海拔$(a)$、距离$(l)$。　　有$Q$组询问，每组询问两个数$v,p$，表示询问从点$v$出发，从第一次走海拔高度...

原文链接http://www.cnblogs.com/zhouzhendong/p/9010945.html　　在一个有边权的无向图中，我们定义$S$和$T$的最小割为，要使得不存在$S$和$T$之间的路径需要删去的边的最小边权和。给定$N×N$的二维数组$A$，你可以令数组的任意元素加上一个非负整数（每个...

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。第一行三个数N，M，Q。第二行N个数，第i个数为h_i接...

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。第一行三个数N，M，Q。第二行N个数，第i个数为h_i接...

　　N个点的图，M条带权边。（N<=100000,M<=1000000）　　有Q次操作(Q<=100000)　　操作有两个类型：　　1.问节点x到y的路径中边的最大权值。　　2.删除某一条边　　操作过程中保证图连通　　我们发现很难做。　　能够1A也是我运气好。　　我们发现顺着做貌似很难，要找到边，然后...

TheUniqueMSTTimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:35999 Accepted:13145DescriptionGivenaconnectedundirectedgraph,tellifitsminimumspanning...

ConstructingRoadsTimeLimit:2000/1000MS(Java/Others)   MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):28154   AcceptedSubm...

还是畅通工程TimeLimit:4000/2000MS(Java/Others)   MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):58241   AcceptedSubmission(s):2...