N个点M条边的无向连通图,每条边有一个权值,求该图的最小生成树。
Input
第1行:2个数N,M中间用空格分隔,N为点的数量,M为边的数量。(2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行:每行3个数S E W,分别表示M条边的2个顶点及权值。(1 <= S, E <= N,1 <= W <= 10000)
Output
输出最小生成树的所有边的权值之和。
Input示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8
Output示例
37
第一种:vector数组实现。
#include<bits/stdc++.h>
using namespace std;
struct stu{
int x;
int y;
int cost;
};
int f[105];
int find(int x){
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
bool unite(int x,int y){ //并查集
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{f[fx]=fy;
return true; //给出提示,假如合并了返回真值
}
return false;
}
bool cmp(stu a,stu b){
return a.cost<b.cost; //权值从小到大排序
}
int main(){
int n,m;
stu r;
vector<stu> v;
while(~scanf("%d%d",&n,&m)&&n){
v.clear();
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&r.x,&r.y,&r.cost);
v.push_back(r);
}
sort(v.begin(),v.end(),cmp);
int sum=0,cnt=0;
for(int i=0;i<v.size();i++){
if(unite(v[i].x,v[i].y)){
sum+=v[i].cost;
cnt++;
}
if(cnt==n-1)
break;
}
printf("%d\n",sum);
}
return 0;
}
2.也可以直接结构体数组,可能这个内存大点.
#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
const int maxm=50010;
int f[maxn];
struct edge{
int u,v;
int len;
}e[maxm];
bool cmp(edge a,edge b){
return a.len<b.len;
}
void init(int n){//初始化并查集
for(int i=1;i<=n;i++)
f[i]=i;
}
int find(int x){
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
int unite(int x,int y){ //合并两个集合(如果x,y在同一集合,返回0,否则返回1)
int fx=find(x);
int fy=find(y);
if(fx!=fy){
f[fx]=fy;
return 1;
}
return 0;
}
int main(){
int m,n;
while(~scanf("%d%d",&n,&m)){
init(n);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].len);
}
sort(e+1,e+m+1,cmp); //注意!这里千万不能错,注意排序范围
int sum=0;
for(int i=1;i<=m;i++){
{
sum+=e[i].len*unite(e[i].u,e[i].v); //不必再加个ant来优化循环了
} //通过unite(i,j)的值决定加不加
} //本质上意思和用if语句那个一样
printf("%d\n",sum);
}
return 0;
}
第二种在最后计算sum的步骤里,可能语句稍微简洁点,但是数据量大的情况下,还是第一种占用内存少.