算法学习
C++ 及算法
C++博客
首页
新随笔
联系
管理
Pku 1258 Agri-Net
#include
<
stdio.h
>
#include
<
string
.h
>
#include
<
limits.h
>
#define
N 110
int
n,result;
int
map[N][N];
bool
visite[N];
int
dis[N];
void
Prim()
{
memset( visite,
false
,
sizeof
(visite) );
visite[
0
]
=
true
; result
=
0
;
for
(
int
i
=
0
; i
<
n;
++
i ) dis[i]
=
map[
0
][i];
for
(
int
i
=
1
; i
<
n;
++
i )
{
int
min
=
INT_MAX, k;
for
(
int
j
=
0
; j
<
n;
++
j )
if
(
!
visite[j]
&&
dis[j]
<
min ) min
=
dis[j], k
=
j;
visite[k]
=
true
; result
+=
dis[k];
for
(
int
j
=
0
; j
<
n;
++
j )
if
(
!
visite[j]
&&
map[k][j]
>
0
&&
map[k][j]
<
dis[j] )
dis[j]
=
map[k][j];
}
}
int
main()
{
while
( scanf(
"
%d
"
,
&
n)
!=
EOF )
{
for
(
int
i
=
0
; i
<
n;
++
i )
for
(
int
j
=
0
; j
<
n;
++
j )
scanf(
"
%d
"
,
&
map[i][j] );
Prim();
printf(
"
%d\n
"
, result );
}
return
0
;
}
posted on 2008-11-05 16:30
Darren
阅读(245)
评论(0)
编辑
收藏
引用
所属分类:
图论
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
Pku 3169 Layout
Pku 1986 Distance Queries
Pku 1258 Agri-Net
Pku 1047 Round and Round We Go
Pku 1089 Intervals
Pku 1062 昂贵的聘礼
Pku 1094 Sorting It All Out
pku 1797 Heavy Transportation
pku 2253 Frogger
PKU 1018 Communication System
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
留言簿
(5)
给我留言
查看公开留言
查看私人留言
随笔分类
动态规划(13)
数据结构(11)
搜索(9)
图论(10)
未分类(6)
ACMers
搜索
积分与排名
积分 - 107922
排名 - 227
最新随笔
1. 换个博客,重新开始学习。。。
2. pku 1691 Painting A Board 状态压缩DP
3. HDU 1255
4. PKU 1151
5. 2009年ACM-ICPC亚洲区预选赛共设十五个赛区如下(按现场赛日期排序)
6. acmer必看的26个对acm态度
7. ZJU 3228 Searching the String ( AC 自动机 )
8. Pku 3169 Layout
9. Pku 1986 Distance Queries
10. Pku 1276 Cash Machine
最新评论
1. re: AVL树的插入和删除操作
评论内容较长,点击标题查看
--jasonkent27@163.com