cucumber
cucumber
poj3259 WormHoles Spfa || BellmanFord
1) Bellman Ford算法找负环的应用.
#include
<
cstdio
>
#include
<
cstdlib
>
#include
<
queue
>
#include
<
deque
>
using
namespace
std;
struct
Node
{
int
to;
int
weight;
Node
*
next;
}
;
#define
MAXFIELD (1000 + 10)
#define
MAXPATH (2500 + 10)
#define
MAXWORMHOLE (200 + 10)
Node nodeHead[MAXFIELD];
Node nodes[MAXPATH
*
2
+
MAXWORMHOLE];
int
dis[MAXFIELD
+
1
];
bool
isInQueue[MAXFIELD
+
1
];
int
allocPos
=
0
;
Node
*
getNode()
{
return
nodes
+
allocPos
++
;
}
void
initGraph(
int
n)
{
allocPos
=
0
;
int
i
=
0
;
for
(i
=
0
; i
<
n;
++
i)
{
nodeHead[i].next
=
NULL;
dis[i]
=
0
;
}
}
void
addEdge(
int
from,
int
to,
int
timeNeed)
{
Node
*
newNode
=
getNode();
newNode
->
next
=
nodeHead[from].next;
newNode
->
to
=
to;
newNode
->
weight
=
timeNeed;
nodeHead[from].next
=
newNode;
}
int
main()
{
int
caseCount, fieldCount, pathCount, wormHoleCount;
int
i, j, from, to, timeNeed;
scanf(
"
%d
"
,
&
caseCount);
for
(i
=
0
; i
<
caseCount; i
++
)
{
scanf(
"
%d%d%d
"
,
&
fieldCount,
&
pathCount,
&
wormHoleCount);
initGraph(fieldCount
+
1
);
for
(j
=
0
; j
<
pathCount; j
++
)
{
scanf(
"
%d%d%d
"
,
&
from,
&
to,
&
timeNeed);
addEdge(from, to, timeNeed);
addEdge(to, from, timeNeed);
}
for
(j
=
0
; j
<
wormHoleCount;
++
j)
{
scanf(
"
%d%d%d
"
,
&
from,
&
to,
&
timeNeed);
addEdge(from, to,
-
timeNeed);
}
//
关键: 按照题目的要求, 可以看出是找图中有没有负环
//
引入一个超级点s, s能够到达任意一个field, 但是没有任何field能够到达s
//
然后如果图中不存在负环, 则在经过fieldCount次松弛(我叫优化)以后,
//
就没有办法使任意一个field节点的权值变小了, 而如果存在负环,
//
则还能松弛/优化.
//
这就是为什么初始化时需要把所有的field都压入队列.
deque
<
int
>
q;
for
(j
=
1
; j
<=
fieldCount;
++
j)
{
q.push_back(j);
isInQueue[j]
=
true
;
}
bool
answer
=
false
;
int
round
=
0
;
while
(
!
q.empty())
{
int
n
=
q.size();
for
(j
=
0
; j
<
n; j
++
)
{
int
u
=
q.front();
q.pop_front();
isInQueue[u]
=
false
;
Node
*
tra;
for
(tra
=
nodeHead[u].next; tra
!=
NULL; tra
=
tra
->
next)
{
int
temp
=
tra
->
weight
+
dis[u];
if
(temp
<
dis[tra
->
to])
{
dis[tra
->
to]
=
temp;
if
(
!
isInQueue[tra
->
to])
{
q.push_back(tra
->
to);
isInQueue[tra
->
to]
=
true
;
}
}
}
}
round
++
;
if
(round
>
fieldCount)
{
answer
=
true
;
q.clear();
break
;
}
}
if
(answer)
{
puts(
"
YES
"
);
}
else
{
puts(
"
NO
"
);
}
}
return
0
;
}
posted on 2011-07-06 01:20
cucumber
阅读(389)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © cucumber
<
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
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 3
文章 - 0
评论 - 0
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
2011年7月 (3)
搜索
最新评论
阅读排行榜
1. poj3259 WormHoles Spfa || BellmanFord(389)
2. poj1062 昂贵的婚礼(354)
3. poj1860 Currency Exchange: spfa / Bellman Ford(330)
评论排行榜
1. poj1860 Currency Exchange: spfa / Bellman Ford(0)
2. poj1062 昂贵的婚礼(0)
3. poj3259 WormHoles Spfa || BellmanFord(0)