细草微风岸
平凡而不平庸
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2011年7月
>
日
一
二
三
四
五
六
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
2011年8月 (1)
2011年7月 (6)
阅读排行榜
1. ECNU_1802_HDU_1022 铁路调度(325)
2. PKU_1015(257)
3. zoj 3339 spfa(249)
4. hdu 3339 0-1背包+最短路(193)
5. zz KMP (matrix67分析得很有条理) (192)
评论排行榜
1. ECNU_1802_HDU_1022 铁路调度(0)
2. HDU_3342_Floy判断环(0)
3. PKU_1258 MST(0)
4. PKU_1015(0)
5. zoj 3339 spfa(0)
常用链接
我的随笔
我的评论
我参与的随笔
统计
随笔 - 7
文章 - 0
评论 - 0
引用 - 0
最新评论
PKU_1258 MST
//
Kruskal
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
#define
clr(a) memset(a,-1,sizeof(a))
#define
MAXN 101
#define
INF 100001
int
dis[MAXN][MAXN];
//
Kruskal,
//
并查集
int
parent[MAXN];
int
rank[MAXN];
int
A[MAXN
*
MAXN
/
2
];
int
e_X[MAXN
*
MAXN
/
2
];
int
e_Y[MAXN
*
MAXN
/
2
];
int
d[MAXN
*
MAXN
/
2
];
void
MakeSet(
int
x)
{
parent[x]
=
x;
rank[x]
=
0
;
}
int
Find(
int
x)
{
if
(parent[x]
==
x)
return
x;
else
{
parent[x]
=
Find(parent[x]);
//
路径压缩
return
parent[x];
}
}
void
Union(
int
x,
int
y)
{
int
xRoot
=
Find(x);
int
yRoot
=
Find(y);
if
(rank[xRoot]
>
rank[yRoot])
//
rank优化
parent[yRoot]
=
xRoot;
else
if
(rank[xRoot]
<
rank[yRoot])
parent[xRoot]
=
yRoot;
else
if
(xRoot
!=
yRoot)
{
parent[yRoot]
=
xRoot;
rank[xRoot]
+=
1
;
}
}
//
最小堆先自己写,熟练后用STL的优先队列
void
sift_up(
int
i)
{
bool
done
=
false
;
int
temp;
if
(i
==
1
)
return
;
while
(i
!=
1
&&
!
done)
{
if
(d[A[i]]
<
d[A[i
/
2
]])
{
temp
=
A[i];
A[i]
=
A[i
/
2
];
A[i
/
2
]
=
temp;
}
else
done
=
true
;
i
/=
2
;
}
}
void
sift_down(
int
i,
int
n)
{
bool
done
=
false
;
int
temp;
if
((
2
*
i)
>
n)
return
;
while
((
2
*
i)
<=
n
&&
!
done)
{
i
*=
2
;
if
((i
+
1
)
<=
n
&&
d[A[i
+
1
]]
<
d[A[i]])
i
+=
1
;
if
(d[A[i
/
2
]]
>
d[A[i]])
{
temp
=
A[i
/
2
];
A[i
/
2
]
=
A[i];
A[i]
=
temp;
}
else
done
=
true
;
}
}
void
Delete(
int
i,
int
&
n)
{
int
x
=
A[i];
int
y
=
A[n];
n
-=
1
;
if
(i
==
(n
+
1
))
return
;
A[i]
=
y;
if
(d[y]
<=
d[x])
sift_up(i);
else
sift_down(i,n);
}
int
delete_min(
int
&
n)
{
int
x
=
A[
1
];
Delete(
1
,n);
return
x;
}
void
MakeHeap(
int
n)
{
int
i ;
for
(i
=
n
/
2
; i
>=
1
; i
--
)
{
sift_down(i,n);
}
}
int
Kruskal(
int
n)
{
int
i,j,count
=
0
,ans
=
0
,x;
clr(parent);
clr(rank);
int
k
=
1
;
for
(i
=
0
; i
<
n;i
++
)
for
(j
=
i
+
1
; j
<
n;j
++
)
{
d[k]
=
dis[i][j];
e_X[k]
=
i;
e_Y[k]
=
j;
A[k]
=
k;
k
++
;
}
MakeHeap(k
-
1
);
for
(i
=
0
; i
<
n; i
++
)
MakeSet(i);
int
N
=
k
-
1
;
while
(count
<
(n
-
1
))
{
x
=
delete_min(N);
if
(Find(e_X[x])
!=
Find(e_Y[x]))
{
count
++
;
ans
+=
d[x];
Union(e_X[x],e_Y[x]);
}
}
return
ans;
}
int
main()
{
int
n,i,j;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
{
for
(i
=
0
; i
<
n;i
++
)
for
(j
=
0
; j
<
n; j
++
)
scanf(
"
%d
"
,
&
dis[i][j]);
printf(
"
%d\n
"
,Kruskal(n));
}
}
//
Prim:
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
#define
clr(a) memset(a,-1,sizeof(a))
#define
MAXN 101
#define
INF 100001
int
dis[MAXN][MAXN];
//
prim
int
C[MAXN];
int
N[MAXN];
int
visit[MAXN];
int
prim(
int
n)
{
int
i,j,k,min,ans
=
0
;
//
首先选择第个点作为起始点
for
(i
=
0
; i
<
n;i
++
)
{
C[i]
=
dis[i][
0
];
//
N[i] = 0;
visit[i]
=
0
;
}
visit[
0
]
=
1
;
for
(i
=
0
; i
<
(n
-
1
); i
++
)
{
min
=
INF;
for
(j
=
0
; j
<
n;j
++
)
{
if
(C[j]
<
min
&&
visit[j]
==
0
)
{
min
=
C[j];
k
=
j;
//
此处肯定有最小值,因为每条边都存在。
}
}
visit[k]
=
1
;
//
加入新的点
ans
+=
C[k];
for
(j
=
0
;j
<
n;j
++
)
{
if
(visit[j]
==
0
&&
C[j]
>
dis[k][j])
{
C[j]
=
dis[k][j];
N[j]
=
k;
}
}
}
return
ans;
}
int
main()
{
int
n,i,j;
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
{
for
(i
=
0
; i
<
n;i
++
)
for
(j
=
0
; j
<
n; j
++
)
scanf(
"
%d
"
,
&
dis[i][j]);
printf(
"
%d\n
"
,prim(n));
}
}
posted on 2011-07-27 00:08
鲍青
阅读(136)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 鲍青