最小生成树（MST）Kruskal算法 + hdu三道例题
#最小生成树 （MST）
标签（空格分隔）： 算法思想
在无向图中，连通且不含 圈 的图称为树。 给定无向图G = （V,E），连接G中所有点，且边集是E的子集的树称
为G的生成树，而权值最小的生成树称为最小生成树（MST）
常见算法： Kruskal 算法 和 Prim 算法。
圈指的是任选一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径称为圈。(可以类似理解成欧拉回路，那就要求奇数度的点为0）Kruskal 算法
Kruskal 算法第一步是给所有边按照从小到大的顺序进行排列（可以用algorithm 自带的sort)。
接下来从小到大考察每条边(u,v)。
情况1： u和v在同一个连通分量**（连通分量的概念）**，那么加入(u,v)之后会形成环，因此不能选择。
情况2： 如果u和v在不同的连通分量(也可以想成是树)，那么加入(v,v)之后一定是最优的。
伪代码:
把所有边排序，记第i小的边为e[i] (i<=i/*
最小生成树(MST) Krustal算法
伪代码:
把所有边排序，记第i小的边为e[i] (i<=i例题：
hdu-1233 还是畅通工程
#include
#include
using namespace std;
const int MAX = 1e5+5;
struct Node{
int x;
int y;
int length;
bool operator < (const Node & h){
return length>n && n){
int m = n*(n-1)/2;
int x,y,l;
for(int i=0;
i<=n;
i++){
pre[i] = i;
}
for(int i=0;
i>x>>y>>l;
node[i] = {x,y,l};
}
sort(node,node+m);
// 最小生成树
int total=0;
int totalcost=0;
while(total hdu-1875 畅通工程再续
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAX = 1e5+5;
struct Node
{
int x;
int y;
double length;
bool operator < (const Node & h){
return length vec[MAX];
int pre[MAX];
int Find(int x)
{
int ans = x;
while(pre[ans]!=ans){
ans = pre[ans];
}
pre[x] = ans;
return ans;
}
double func(int x1,int x2,int y1,int y2)
{
return sqrt(pow(x1-x2,2)+pow(y1-y2,2));
}
bool vis[MAX];
int main()
{
int T;
cin>>T;
while(T--){
int n;
cin>>n;
//小岛个数
memset(vis,0,sizeof(vis));
for(int i=1;
i<=n;
i++){
pre[i] = i;
}
int x,y;
for(int i=1;
i<=n;
i++){
cin>>x>>y;
island[i] = Island{x,y};
}
int cnt=0;
int tot=0;
for(int i=1;
i<=n;
i++){
for(int j=1;
j<=n;
j++){
if(i==j)
continue;
double l = func(island[i].x,island[j].x,island[i].y,island[j].y);
if(l>=10 && l<=1000){ //这两个点可以相连啊
node[cnt++] = Node{i,j,l};
}
}
}
sort(node,node+cnt);
// 最小生成树
int total=0;
double totalcost=0;
for(int i=0;
i 【最小生成树（MST）Kruskal算法 + hdu三道例题】hdu-1301
#include
#include
using namespace std;
const int MAX =1e5+5;
struct Node
{
int x;
int y;
int length;
bool operator < (const Node & h)
{
return length> n && n){
char viliage;
int k;
for(int i=0;
i<=n;
i++){
pre[i] = i;
}
int cnt=0;
//记录边数
for(int i=0;
i>viliage>>k;
char ch;
int l;
for(int i=0;
i>ch>>l;
road[cnt++] = Node{ viliage-'A'+1, ch-'A'+1,l};
//把所有的路都记录下来
}
}
sort(road,road+cnt);
int totalcost=0;
int tot=0;
for(int i=0;
i 推荐阅读
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- java中如何实现重建二叉树
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- 记录iOS生成分享图片的一些问题，根据UIView生成固定尺寸的分享图片
- ssh生成公钥秘钥
- 白杨树
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会
- ［原创］能见沂山一棵树，胜读十年无用书！
- 涵养字外功
- 2018.07.07《刺杀骑士团长》村上春树