POJ 3026 Borg Maze （最小生成树）
Borg Maze题目链接：http://acm.hust.edu.cn/vjudge/contest/124434#problem/IDescriptionThe Borg is an immensely powerful race of enhanced humanoids from the d...
There is No Alternative~最小生成树变形
DescriptionICPC (Isles of Coral Park City) consist of several beautiful islands.The citizens requested construction of bridges between islands to reso...
HDU 2489 Minimal Ratio Tree（暴力+最小生成树）（2008 Asia Regional Beijing）
DescriptionFor a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation. Given a complete gra...
{POJ}{3925}{Minimal Ratio Tree}{最小生成树}
题意：给定完全无向图，求其中m个子节点，要求Sum(edge)/Sum(node)最小。思路：由于N很小，枚举所有可能的子节点可能情况，然后求MST，memset()在POJ G++里面需要cstring头文件。#include <iostream>#include <vector...
HDU 2489 Minimal Ratio Tree(dfs枚举+最小生成树)
想到枚举m个点，然后求最小生成树，ratio即为最小生成树的边权/总的点权。但是怎么枚举这m个点，实在不会。网上查了一下大牛们的解法，用dfs枚举，没想到dfs还有这么个作用。参考链接：http://blog.csdn.net/xingyeyongheng/article/details/93732...
java实现最小生成树的prim算法和kruskal算法
在边赋权图中，权值总和最小的生成树称为最小生成树。构造最小生成树有两种算法，分别是prim算法和kruskal算法。在边赋权图中，如下图所示:在上述赋权图中，可以看到图的顶点编号和顶点之间邻接边的权值，若要以上图来构建最小生成树。结果应该如下所示:这样构建的最小生成树的权值总和最小，为17在构建最小...
poj 2349 Arctic Network(最小生成树的第k大边证明)
题目链接：http://poj.org/problem?id=2349题目大意：有n个警戒部队，现在要把这n个警戒部队编入一个通信网络，有两种方式链接警戒部队：1,用卫星信道可以链接无穷远的部队.2,用信号收发器可以链接周围d米以内的部队.现在有s个卫星信道，问d最小是多少时能连接全部的警戒部队？解...
POJ 2349 Arctic Network(最小生成树+求第k大边)
题目链接：http://poj.org/problem?id=2349题目大意：有n个前哨，和s个卫星通讯装置，任何两个装了卫星通讯装置的前哨都可以通过卫星进行通信，而不管他们的位置。 否则，只有两个前哨之间的距离不超过D，才能通过无线电进行通信。求出能使所有前哨都能直接或间接通信的最小的D。解题思...
poj 2349 Arctic Network 最小生成树，求第k大条边
题目抽象出来就是有一些告诉坐标的通信站，还有一些卫星，这些站点需要互相通信，其中拥有卫星的任意两个站可以不用发射器沟通，而所有站点的发射器要都相同，但发射距离越大成本越高。输入的数据意思：实例个数卫星个数 站点个数每个站点的坐标输出的意思：发射器最小是多少，保留两位小数注意事项：其中卫星数量少于...
BZOJ2429[HAOI2006]聪明的猴子[最小生成树 kruskal]
2429: [HAOI2006]聪明的猴子Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 896 Solved: 575[Submit][Status][Discuss]Description在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天...
Poj(2349)，最小生成树的变形
题目链接：http://poj.org/problem?id=2349Arctic NetworkTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 17032 Accepted: 5441DescriptionThe Departme...
POJ2485 最小生成树
问题：POJ2485本题求解生成树最大边的最小值分析：首先证明生成树最大边的最小值即最小生成树的最大边。假设：生成树最大边的最小值比最小生成树的最大边更小。不妨设C为G的一个最小生成树，e是其中的最大边。把e从C中去除，则C被分成C1，C2两个连通子集。假设存在最大边小于e的生成树CC，则CC中连接...
【2018 ICPC亚洲区域赛徐州站 A】Rikka with Minimum Spanning Trees（求最小生成树个数与总权值的乘积）
Hello everyone! I am your old friend Rikka. Welcome to Xuzhou. This is the first problem, which is a problem about the minimum spanning tree (MST). I ...
spoj 104 Highways (最小生成树计数)
题目链接：http://www.spoj.pl/problems/HIGH/题意：求最小生成树个数。 #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #inc...
最小生成树之Kruskal
模板题，学习一下最小生成树的Kruskal算法对于一个连通网（连通带权图，假定每条边上的权均为大于零的实数）来说，每棵树的权（即树中所有边的权值总和）也可能不同具有权最小的生成树称为最小生成树生成树：无向连通图的边的集合无回路连接所有的点最小：所有边的权值之和最小n个顶点的树有n-1条边时间复杂度：...
POJ 2031 Building a Space Station (最小生成树)
Building a Space StationTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 5173 Accepted: 2614DescriptionYou are a member of the space station ...
最小生成树练习。。。
http://poj.org/problem?id=1789 很裸的一道最小生成树题目，就是建立map[][]后直接套模板。。。。 http://poj.org/problem?id=2485 求最小生成树中的最大权值。。。做这个题时犯了个很2的错误，贡献了好几次WA。。最后重敲了一遍A了。。不说...
HDU 1162 Eddy's picture 最小生成树
Eddy's pictureTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 164 Accepted Submission(s): 120 ...
[51nod1213]二维曼哈顿距离最小生成树
二维平面上有N个坐标为整数的点，点x1 y1同点x2 y2之间的距离为：横纵坐标的差的绝对值之和，即：Abs(x1 - x2) + Abs(y1 - y2)（也称曼哈顿距离）。求这N个点所组成的完全图的最小生成树的边权之和。Input第1行：1个数N，表示点的数量。(2 <= N <= ...
HDU--1301--Jungle Roads（最小生成树）
Problem DescriptionThe Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between vil...