文档章节

畅通工程

1
 1944864971
发布于 2016/07/24 12:00
字数 284
阅读 5
收藏 0

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
const int MaxSize=105;
const int INF=0x3f3f3f3;
using namespace std;
int Graph[MaxSize][MaxSize];
int dis[MaxSize];
int op[MaxSize];
int vest[MaxSize];
int N,M;
void prime()
{
for(int i=1;i<=M;i++)
{
dis[i]=Graph[1][i];
op[i]=0;
}
int flag=0;
op[1]=1;
int sum=0;
for(int k=1;k<M;k++)
{
int Min=INF;
flag=0;
for(int i=1;i<=M;i++)
if(op[i]==0&&dis[i]<Min)
{
flag=i;
Min=dis[i];
}
op[flag]=1;
sum+=Min;
for(int i=1;i<=M;i++)
if(op[i]==0&&Graph[flag][i]<dis[i])
dis[i]=Graph[flag][i];
}

printf("%d\n",sum);

}
int Find (int t)
{
if(vest[t]==0)return t;
return Find(vest[t]);
}
void HeBing(int a,int b)
{
int x=Find(a);
int y=Find(b);
if(x!=y)vest[x]=y;
}
int main()
{
while(scanf("%d",&N),N)
{

scanf("%d",&M);
for(int i=0;i<=M;i++)
for(int j=0;j<=M;j++)
Graph[i][j]=0x3f3f3f3f;
int a,c,b,count=0;
for(int i=1;i<=M;i++)
vest[i]=0;
for(int i=1;i<=N;i++)
{
scanf("%d%d%d",&a,&b,&c);
HeBing(a,b);//将两条联通的道路合并在一个集合
Graph[a][b]=Graph[b][a]=c;
}
for(int i=1;i<=M;i++)
if(vest[i]==0)++count;
if(count-1!=0)printf("?\n");//判断是否全部在一个 集合内,即是否连通
else
prime();
}
return 0;
}

 

本文转载自:http://www.cnblogs.com/aaaadengchaochao/p/5041372.html

1
粉丝 0
博文 57
码字总数 0
作品 0
郑州
私信 提问
hdu-1979-继续畅通工程

原文链接:hdu-1979-继续畅通工程 原文: 继续畅通工程 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 26600 Accepted Submiss......

Big_laoshu
2017/11/20
0
0
hdu-1874-畅通工程续

原文链接: hdu-1874-畅通工程续 原文: 畅通工程续 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 58577 Accepted Submission(......

Big_laoshu
2017/11/23
0
0
hdu--1863--畅通工程

畅通工程Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 33469 Accepted Submission(s): 14815 Problem Description 省政府“畅通......

king_cannon_fodder
2017/12/13
0
0
1.1.1最短路(Floyd、Dijstra、BellmanFord)

转载自hr_whisper大佬的博客 一、Dijkstra 比较详细的迪杰斯特拉算法讲解传送门 Dijkstra单源最短路算法,即计算从起点出发到每个点的最短路。所以Dijkstra常常作为其他算法的预处理。 使用邻...

fire_to_cheat_
2018/03/04
0
0
Scala and Maven

构建Scala的工程常用sbt,sbt固然灵活,功能强大,却也难以精通,且在国内使用往往遇到网络不畅通的情况。虽然可以使用Repox公服和Coursier加速,却也浪费程序员们宝贵的时间。 Maven虽然死板...

碎镜
2017/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
2K
14
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
38
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
40
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
61
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部