九度oj 题目1347：孤岛连通工程
2024-09-07 11:07:48
- 题目描述：
-
现在有孤岛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 <cstdio>
#include <algorithm>
#define max_v 1002
#define max_m 10002
struct Edge{
int from, to, dis;
};
int par[max_v];
int rank[max_v]; int cmp(const void *a, const void *b) {
Edge at = *(Edge *)a;
Edge bt = *(Edge *)b;
return at.dis - bt.dis;
}
int ini(int N) {
for(int i = ; i <= N; i++) {
par[i] = i;
rank[i] = ;
}
}
int find(int t) {
if(t == par[t]) {
return t;
}
else {
return par[t] = find(par[t]);
}
} Edge e[max_m];
int n, m;
int main(int argc, char const *argv[])
{
freopen("input.txt","r",stdin);
while(scanf("%d %d",&n,&m) != EOF) {
for(int i = ; i < m; i++) {
scanf("%d %d %d",&e[i].from, &e[i].to, &e[i].dis);
}
qsort(e, m, sizeof(Edge), cmp);
int ans = ;
int cnt = ;
ini(n);
for(int i = ; i < m; i++) {
int a = e[i].from;
int b = e[i].to;
int c = e[i].dis;
//printf("%d %d %d\n",a,b,c);
a = find(a);
b = find(b);
if(a == b) {
continue;
}
if(a != b) {
ans = ans + c;
if(rank[a] < rank[b]) {
par[a] = b;
}
else {
par[b] = a;
rank[a]++;
}
cnt++;
if(cnt == n-) {
break;
}
}
}
if(cnt == n-) {
printf("%d\n",ans);
}
else {
puts("no");
}
}
return ;
}
最新文章
- Server Tomcat v7.0 Server at localhost was unable to&amp;nbs 报错问题解决
- execl表格VLOOKUP函数的使用
- canvas缓动2
- FIL Dalian Jobs
- lambda的Func<>函数
- POJ2516 Minimum Cost（最小费用最大流）
- Eclipse 反编译器
- BZOJ 1607: [Usaco2008 Dec]Patting Heads 轻拍牛头 筛法
- javascript 上传 预览图片 兼容 谷歌 ie
- mysql语法充电
- iOS 之 内存管理
- selenium实现自动下载文件
- replicated mode vs global mode - 每天5分钟玩转 Docker 容器技术（105）
- Android简易实战教程--第三十八话《自定义通知NotifiCation》
- 关闭 Mac 拼写自动纠正与横线转换
- RESTful-1概述
- 浅谈js中的this关键字
- ODAC（V9.5.15) 学习笔记（十四）TCRBatchMove
- 转Generative Model 与 Discriminative Model
- Select count(*)、Count(1)、Count(0)的区别和执行效率比较