SDUT-2144_最小生成树
2024-09-06 02:27:13
数据结构实验之图论九:最小生成树
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
有n个城市,其中有些城市之间可以修建公路,修建不同的公路费用是不同的。现在我们想知道,最少花多少钱修公路可以将所有的城市连在一起,使在任意一城市出发,可以到达其他任意的城市。
Input
输入包含多组数据,格式如下。
第一行包括两个整数n m,代表城市个数和可以修建的公路个数。(n <= 100, m <=10000)
剩下m行每行3个正整数a b c,代表城市a 和城市b之间可以修建一条公路,代价为c。
Output
每组输出占一行,仅输出最小花费。
Sample Input
3 2
1 2 1
1 3 1
1 0
Sample Output
2
0
题解:prim算法来求最小生成树,同SDUT-3362_村村通公路。
不过这道题更简单点,不用判定是否连通,题目貌似都是连通的数据。
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int s[1050][1050];/*利用邻接矩阵来记录图*/
int n;/*n节点数量*/
int f[1050];/*记录点是否被遍历过*/
int INF = 1e9+7;/*相当于无穷大*/
int prim()
{
int i,sum,j,MIN,k;
int dis[1050];
for(i=1;i<=n;i++)
{
f[i] = 0;
dis[i] = s[1][i];
}
f[1] = 1;
sum = 0;
for(i=1;i<n;i++)
{
MIN = INF;
k = -1;
for(j=1;j<=n;j++)
{
if(!f[j]&&dis[j]<MIN)
{
MIN = dis[j];
k = j;
}
}
f[k] = 1;
sum += MIN;
for(j=1;j<=n;j++)
{
if(!f[j]&&dis[j]>s[k][j])
dis[j] = s[k][j];
}
}
return sum;
}
int main()
{
int m,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s[i][j] = i==j?0:INF;
for(i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c<s[a][b])
s[a][b] = s[b][a] = c;
}
printf("%d\n",prim());
}
return 0;
}
最新文章
- Win10开始菜单打不开?两个办法可破
- (1)c语言学习总结之从关键字到循环结构
- CAsyncSocket
- 我的学习记录JAVA第二天
- AJax的异步请求
- three.js粒子效果(分别基于CPU&;GPU实现)
- POJ 3923 HDU 2487 Ugly Windows 简单计算
- mysql修改表和列
- matplotlib画散点图,并在散点处打上相应标签
- linux:gpg加密和解密
- reveal 使用注意事项
- 性能测试-6.VUG脚本参数化
- WINDOWS防火墙开启后Ping不通
- 8.8 正睿暑期集训营 Day5
- PHP打开空白的解决办法
- java.lang.NoClassDefFoundError: org/hamcrest/SelfDescribing,
- Exception in thread main java.lang.NoClassDefFoundError: org/apache/juli/logging/LogFacto
- 使用opencv3+python实现视频运动目标检测
- Bzoj[Usaco2018 Feb]5194 Snow Boots(线段树)
- 原型设计工具Mockplus新年送福利,见者有份