孤岛连通工程
作者：Hackbuteer1 发表于2012-2-16 19:31:49 原文链接题目描述：
现在有孤岛n个，孤岛从1开始标序一直到n，有道路m条（道路是双向的，如果有多条道路连通岛屿i，j则选择最短的那条），请你求出能够让所有孤岛都连通的最小道路总长度。
输入：
数据有多组输入。
每组第一行输入n(1<=n<=1000),m(0<=m<=10000)。
接着m行，每行输入一条道路i j d(0<=d<=1000)，（i,j表示岛屿序号，d表示道路长度）。
输出：
对每组输入输出一行，如果能连通，输出能连通所有岛屿的最小道路长度，否则请输出字符串"no"。
样例输入：3 5
1 2 2
1 2 1
2 3 5
1 3 3
3 1 2
4 2
1 2 3
3 4 1样例输出：3
no
#include<iostream>
#include<algorithm>
using namespace std;
#include<stdio.h>
struct Edge
{
int x;
int y;
int cost;
}edge;
int set;
inline int find(int x) //带路径优化的并查集查找算法
{
int i,j,r;
r=x;
while(set!=r)
r=set;
i=x;
while(i!=r)
{
j=set;
set=r;
i=j;
}
return r;
}
inline void merge(int x,int y) //优化的并查集归并算法
{
int t=find(x);
int h=find(y);
if(t<h)
set=t;
else
set=h;
}
/*
int cmp(const void *a,const void *b)
{
return((*(struct Edge *)a).cost-(*(Edge *)b).cost);
}
*/
bool cmp(const Edge& a,const Edge& b)
{
return a.cost<b.cost;
}
void init(int n) //初始化并查集，各点为孤立点，分支数为n
{
for(int i=1;i<=n;i++)
set=i;
}
int kruskal(int n,int m)
{
int i,num,sum,from,to;
//qsort(edge,m,sizeof(edge),cmp);
sort(edge,edge+m,cmp);
sum=num=0;
for(i=0;i<m;i++)
{
from = find(edge.x); //判断线段的起始点所在的集合
to = find(edge.y); //判断线段的终点所在的集合
if(from != to) //如果线段的两个端点所在的集合不一样
{
merge(from,to); //合并两个集合
sum+=edge.cost;
num++;
}
if(num==n-1)
break;
}
if(num<n-1)
return -1;
else
return sum;
}
int main(void)
{
int i,n,m,k;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
{
scanf("%d %d %d",&edge.x,&edge.y,&edge.cost);
}
init(n);
k=kruskal(n,m);
if(k==-1)
printf("no\n");
else
printf("%d\n",k);
}
return 0;
}
页:
[1]