prim和kruskal算法比较
kruskal在生成最小树之前，所有边权重都直接排序，prim多次寻找权重最小的邻居，所以在时间上kruskal比prim更快。
题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
样例解释：
因此，最小生成树的总边权是2 2 3=72 2 3=7。
用kruskal写的模板
#include<bits/stdc .h> using namespace std; const int MAXM=200001; const int MAXN=5001; int n,m;///顶点数，边的条数 long long len;///最小生成树总长 int total; struct node { int b;//起点 int e;//终点 int w;//边权 }edge[MAXM];//创建边集 int par[MAXN];//用于判断是否形成闭环，表示连接该点的下一点类似于并收集 bool cmp(node a,node b)///根据权重从小到大排序边集 { return a.w<b.w; } int Find(int *par,int f)///找到连接顶点的尾部下标 { while(par[f]>0){ f=par[f]; }return f; } void Kruskal()//kruskal算法 { sort(edge 1,edge m 1,cmp);//排序 int x,y; for(int i=1;i<=m;i ){//循环每个边缘 x=Find(par,edge[i].b); y=Find(par,edge[i].e); if(x!=y){//若x=y这意味着两个点连接的尾部是相同的，当前的边缘形成闭环 par[x]=y;////将结尾顶点的下标放入起点顶点par数组值中，表示已存入最小生成树 len =edge[i].w; total ; } if(total==n-1) break; } } int main() { cin>>n>>m; for(int i=1;i<=m;i ){ int p,q,r; cin>>p>>q>>r; edge[i].b=p; edge[i].e=q; edge[i].w=r; } Kruskal(); if(total<n-1) cout<<"orz"<<endl; else cout<<len<<endl; }
题目背景
还记得 NOIP 2011 提高组 Day1 铺地毯？时光飞逝，时光飞逝，三年过去了。组织者精心准备的颁奖典礼已经结束，留下的是人们踩过的地毯。请解决另一个类似地毯的问题。
题目描述
会场上有 n 不同的关键区域由关键区域组成 m 无向地毯相互连接。每个地毯可以有三个整数 u、v、w 表示，其中 u 和 v 编号连接地毯的两个关键区域，w 美丽的地毯。
由于颁奖典礼已经结束，铺好的地毯必须拆除。为了贯彻勤俭节约的原则，组织者被要求只保留 K 在地毯和保留地毯的图片中，只有一种方法可以在任何两点之间到达。换句话说，组织者要求新图片中没有环。现在组织者向你求助，想请你帮忙计算一下 K 最大的美丽之和是多少？
输入格式
第一行包括三个正整数 n、m、K。
接下来 m 每行包含三个正整数 u、v、w。
输出格式
只包含一个正整数，表示这个 K 地毯美丽之和的最大值。
输入输出样例
复制
5 4 3 1 2 10 1 3 9 2 3 7 4 5 3
复制
22
说明/提示
选择第 1、2、4 美丽之和的地毯 10 9 3 = 22。
若选择第 1、2、3 虽然地毯的美丽之和可以达到 10 9 7 = 但这将导致关键区域 1、2、3 标题中不允许形成一个环。
1<=n,m,k<=100000
#include<bits/stdc .h> using namespace std; int n,m,k; long long len; const int MaxNM=100001; int total; struct node { int b; int e; int w; }edge[MaxNM]; int par[MaxNM]; int Find(int *par,int f) { while(par[f]>0){ f=par[f]; }return f; } bool cmp(node a,node b) { return a.w>b.w;///按权重从大到小排列 } void Kru() { sort(edge 1,edge m 1,cmp); int x,y; for(int i=1;i<=m;i ){ x=Find(par,edge[i].b); y=Find(par,edge[i].e); if(x!=y){ par[x]=y; len =edge[i].w; total ; } if(total>=k) break;///地毯数量大于等于k } } int main() { cin>>n>>m>>k; for(int i=1;i<=m;i ){ int z,x,c; cin>>z>>x>>c; edge[i].b=z; edge[i].e=x; edge[i].w=c; } Kru(); cout<<len<<endl; }
题目背景
小杉坐在教室里，透过口袋般的窗户看着口袋般的天空。
那里飘着许多云，看上去很漂亮，小杉想摘下几朵这么漂亮的云，做成棉花糖。
题目描述
给你云的数量NN，再给你MM一种关系意味着哪些云可以连接在一起。
现在小杉想把所有的云连成一个云KK一个棉花糖，一个棉花糖至少要用一朵云，小杉想知道他怎么连，成本最低。
输入格式
第一行有三个数字N,M,KN,M,K。
接下来MM每行三个数X,Y,LX,Y,L，表示XX云和YY云可以通过&nbs;LL 的代价连在一起。
输出格式
对每组数据输出一行，仅有一个整数，表示最小的代价。
如果怎么连都连不出 KK 个棉花糖，请输出 No Answer。
输入输出样例
复制
3 1 2
1 2 1
复制
1
说明/提示
对于 30\%30% 的数据，N \le 100N≤100，M \le 10^3M≤103；
对于 100\%100% 的数据，1 \le N \le 10^31≤N≤103，1 \le M \le 10^41≤M≤104，1 \le K \le 101≤K≤10，1 \le X,Y \le N1≤X,Y≤N，0 \le L<10^40≤L<104。
棉花糖的数目我们可以理解成可以生成的树的数目，则边为n-k时，生成了k棵树。
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long len;
const int MaxN=1001;
const int MaxM=10001;
int total;
struct node
{
int b;
int e;
int w;
}edge[MaxM];
int par[MaxN];
int Find(int *par,int f)
{
while(par[f]>0){
f=par[f];
}return f;
}
bool cmp(node a,node b)
{
return a.w<b.w;
}
void Kru()
{
sort(edge+1,edge+m+1,cmp);
int x,y;
for(int i=1;i<=m;i++){
x=Find(par,edge[i].b);
y=Find(par,edge[i].e);
if(x!=y){
par[x]=y;
len+=edge[i].w;
total++;
}
if(total>=n-k) break;//生成k棵树时，循环结束
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int z,x,c;
cin>>z>>x>>c;
edge[i].b=z;
edge[i].e=x;
edge[i].w=c;
}
Kru();
if(total<n-k){cout<<"No Answer"<<endl;}
else cout<<len<<endl;
}