hdu 1233(最小生成树 prim算法)
2024-08-31 02:35:22
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 43080 Accepted Submission(s): 19636
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
Hint
Hint
Huge input, scanf is recommended.
最小生成树 模版
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cstdlib>
#include<string>
#define eps 0.000000001
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const int N=+;
const int INF=0x3f3f3f3f;
int mp[N][N];
int n;
int vis[N];
int dis[N];
int u,v,w;
void prim(){
int ans=;
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
for(int i=;i<=n;i++)dis[i]=mp[][i];
vis[]=;
for(int i=;i<=n-;i++){
int pos;
int minn=INF;
for(int j=;j<=n;j++){
if(vis[j]==&&minn>dis[j]){
pos=j;
minn=dis[j];
} }
vis[pos]=;
ans=ans+minn;
for(int j=;j<=n;j++){
if(vis[j]==&&dis[j]>mp[pos][j])dis[j]=mp[pos][j];
}
}
cout<<ans<<endl;
}
int main(){
while(scanf("%d",&n)!=EOF){
if(n==)break;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)mp[i][j]=INF;
int m;
if(n%==)m=n/*(n-);
else
m=(n-)/*n;
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
mp[u][v]=w;
mp[v][u]=w;
}
prim();
}
}
最新文章
- js闭包
- PHP如何获取二个日期的相差天数?
- MyBatis学习总结_13_Mybatis查询之resultMap和resultType区别
- Why String is immutable in Java ?--reference
- css filter详解
- 网络流(最大费用最大流) :POJ 3680 Intervals
- Day4 内置函数补充、装饰器
- Quartz.net使用记录
- character-RNN模型介绍以及代码解析
- 常用Jquery插件整理大全
- Flask 源码流程,上下文管理
- ThinkPHP 数据库操作(四) : 聚合查询、时间查询、高级查询
- 用gogs轻松搭建个人的git服务器
- C语言 &#183; 积分之迷
- centos 切换nginx跟apache环境
- leetcode: 638.大礼包
- python中的filter、map、reduce、apply用法
- 关于Thinkphp5类命名导致的“模块不存在”问题
- ASP.NET MVC分页 Ajax+JsRender
- JS判断客户端是否是iOS或者Android端