蜗牛の狂奔笔记
对于蜗牛来说,狂奔虽不代表极速,但展现的却是一种拼尽全力的姿态........
pku 1135
2009年7月29日
题目链接:
PKU 1135 Domino Effect
分类:(Dijkastra+枚举)
题目分析与算法原型
这道题目的意思大致是给你n个骨牌,以及某些骨牌之间的边,这些边的权值代表,从这条边的某一端(某一骨牌)开始倒,一直倒到该边的终点(该边的另一个骨牌)所需的时间,然后题目的求的是,从编号为1的骨牌开始倒(注意,某一个骨牌倒的时候,连同与其相邻的边都同时开始往外面倒),求最后倒的骨牌的位置(在某两个骨牌之间或者是刚给你的n个骨牌的其中一个)并输出时间..........
其实,因为每个牌倒的同时都连带与其连接的所有边也同时倒,不难看出,当从骨牌1一直倒到某个骨牌x的时候,其实从1到x间的路径必定是最短路径,因为肯定是沿着最短的路径才能先到达x么,考虑到这点,问题就已经解决一半了,我们可以先算出从1点出发的到其他所有点的最短路径,然后取这些最短路径中最长的那个点y,然后再枚举所有与这个点相邻的点 (这里需要除去 path[y]这点),假设z是其中一个点,然后找能使得(dis[y]+dis[z]+map[y][z])/2最长的那个点,若(dis[y]+dis[z]+map[y][z])/2>dis[y],则说明最后一个是y,若(dis[y]+dis[z]+map[y][z])/2=dis[y]则说明,最后一个处与y和z之间.........
Code:
1
#include
<
stdio.h
>
2
#define
max 1000000000
3
#define
len 505
4
5
int
n,m,a,b,l,map[len][len],dis[len],visit[len],path[len];
6
7
void
init()
8
{
9
int
i,j;
10
for
(i
=
1
;i
<=
n;i
++
)
11
for
(j
=
1
;j
<=
n;j
++
)
12
{
13
if
(i
==
j)map[i][j]
=
0
;
14
else
map[i][j]
=
max;
15
}
16
}
17
void
Dijkastra(
int
s)
//
s为源点
18
{
19
int
i,j;
20
for
(i
=
1
;i
<=
n;i
++
)
21
{
22
dis[i]
=
map[s][i];
23
visit[i]
=
0
;
24
if
(i
!=
s
&&
dis[i]
<
max)path[i]
=
s;
25
else
path[i]
=-
1
;
26
27
}
28
visit[s]
=
1
;
29
for
(i
=
1
;i
<
n;i
++
)
30
{
31
int
min
=
max,u;
32
for
(j
=
1
;j
<=
n;j
++
)
33
if
(visit[j]
==
0
&&
dis[j]
<
min)
34
{
35
u
=
j;
36
min
=
dis[j];
37
}
38
39
if
(min
==
max)
return
;
//
此语句对于非连通图是必须的,表示当前已经不存在路径了
40
41
visit[u]
=
1
;
42
for
(j
=
1
;j
<=
n;j
++
)
43
if
(visit[j]
==
0
&&
map[u][j]
<
max
&&
dis[u]
+
map[u][j]
<
dis[j])
44
{
45
dis[j]
=
dis[u]
+
map[u][j];
46
path[j]
=
u;
47
}
48
}
49
}
50
int
main()
51
{
52
int
i,ccase
=
1
;;
53
while
(scanf(
"
%d%d
"
,
&
n,
&
m)
!=
EOF)
54
{
55
if
(n
==
0
&&
m
==
0
)
break
;
56
init();
57
for
(i
=
0
;i
<
m;i
++
)
58
{
59
scanf(
"
%d%d%d
"
,
&
a,
&
b,
&
l);
60
if
(l
<
map[a][b])
61
{
62
map[a][b]
=
l;
63
map[b][a]
=
l;
64
}
65
}
66
Dijkastra(
1
);
67
int
_max
=-
1
,num;
68
for
(i
=
1
;i
<=
n;i
++
)
69
{
70
if
(dis[i]
>
_max)
71
{
72
_max
=
dis[i];
73
num
=
i;
74
}
75
}
76
_max
=-
1
;
77
int
pos;
78
for
(i
=
1
;i
<=
n;i
++
)
79
{
80
if
(i
!=
path[num]
&&
map[num][i]
<
max)
81
{
82
if
(dis[num]
+
dis[i]
+
map[num][i]
>
_max)
83
{
84
_max
=
dis[num]
+
dis[i]
+
map[num][i];
85
pos
=
i;
86
}
87
}
88
}
89
printf(
"
System #%d\n
"
,ccase
++
);
90
if
(dis[pos]
+
map[num][pos]
==
dis[num])
91
printf(
"
The last domino falls after %.1f seconds, at key domino %d.\n
"
,(
double
)dis[num],num);
92
else
93
{
94
double
res
=
(
double
)(dis[pos]
+
map[num][pos]
+
dis[num])
/
2
;
95
if
(num
<
pos)
96
printf(
"
The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n
"
,res,num,pos);
97
else
98
printf(
"
The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n
"
,res,pos,num);
99
100
}
101
printf(
"
\n
"
);
102
103
}
104
return
0
;
105
}
106
posted on 2009-07-29 10:14
蜗牛也Coding
阅读(260)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 蜗牛也Coding
<
2009年7月
>
日
一
二
三
四
五
六
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
7
8
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 78
文章 - 0
评论 - 96
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔档案
(78)
2011年7月 (1)
2011年4月 (1)
2010年11月 (4)
2010年10月 (4)
2010年9月 (2)
2010年8月 (7)
2010年3月 (1)
2010年2月 (5)
2009年12月 (2)
2009年10月 (1)
2009年9月 (1)
2009年8月 (16)
2009年7月 (31)
2009年6月 (2)
搜索
积分与排名
积分 - 91683
排名 - 259
最新评论
1. re: 关于 OpenGl
太谢谢了。
--袁锋
2. re: 关于 OpenGl
太感谢!
--芙
3. re: 关于MAC系统win 7虚拟机不能上网的问题[未登录]
.vmx文件在哪里?
--a
4. re: MFC中如何将 CFormView放置到一个CDockablePane中
注释掉的创建部分,指针调用
为何不用友元类声明下,就可以用了的。CreateOne,有点绕。
感谢博主分享。
--ren
5. re: 关于 OpenGl
非常感谢~~
--无叶莲
阅读排行榜
1. pragma comment的使用(转)(17177)
2. MFC中如何将 CFormView放置到一个CDockablePane中(8154)
3. (转)关于OpenGL的安装(4821)
4. 关于 OpenGl(4391)
5. VC 界面窗口,静态分割后如何锁定分隔条或限制分隔条的移动范围(4272)
评论排行榜
1. 据说是来自chrome的代码里的一个模板(13)
2. 关于 OpenGl(10)
3. Visual Studio 历史简介(转)(6)
4. pku 1200(6)
5. 推免--北航(5)