MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
让我读了好长好长时间题。。。。。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3259

不过 一次就过啦,真开心

题意 : 一个famer有一些农场,这些农场里面有一些田地,田地里面有一些虫洞,田地和田地之间有路,虫洞有这样的性质: 时间倒流。

问你这个农民能不能看到他自己,也就是说,有没有这样一条路径,能利用虫洞的时间倒流的性质,让这个人能在这个点出发前回去,这样他就是能看到他自己了。。。。。瀑布汗。。。。

输入 :


2       //农场个数   (text cases)
3 3 1 //田地 路径 虫洞 他们的个数
1 2 2 //田地路径 u, v, 以及经过需要的时间
1 3 4
2 3 1
3 1 3 //虫洞路径 u, v, 以及倒流的时间
3 2 1
1 2 3
2 3 4
3 1 8


想法: 首先建有向图,双向的路径也可以表示,然后倒流的时间设置为负权值。这样,就判断这个图里面有没有负回路就可以了
因为负回路就可以满足条件,代表总共的需要的时间是负的,也就是时间倒流了。

一次bellman。


 1 #include <stdio.h>
 2 #include <string.h>
 3 #define max 10001
 4 #define point 501
 5 using namespace std;
 6 
 7 struct E{
 8     int u, v, w;
 9 }e[25000];
10 int el, n, d[501];
11 
12 void bellman(){
13     int i, j, f = 0;
14     for(i = 0; i < n - 1; i++){
15         f = 0;
16         for(j = 0; j < el; j++){
17             if(d[e[j].v] > d[e[j].u] + e[j].w){
18                 d[e[j].v] = d[e[j].u] + e[j].w;
19                 f = 1;
20             }
21         }
22         if(!f){
23             puts("NO");
24             return;
25         }
26     }
27     for(i = 0; i < el; i++){
28         if(d[e[i].v] > d[e[i].u] + e[i].w){
29             puts("YES");
30             return;
31         }
32     }
33     puts("NO");
34 }
35 
36 int main(){
37     int i, j, m, w, u, v, W, F;
38     scanf("%d"&F);
39     while(F--){
40         el = 0;
41         scanf("%d%d%d"&n, &m, &w);
42         for(i = 0; i < m; i++){
43             scanf("%d%d%d"&u, &v, &W);
44             e[el].u = u;
45             e[el].v = v;
46             e[el++].w = W;
47             e[el].u = v;
48             e[el].v = u;
49             e[el++].w = W;
50         }
51         for(i = 0; i < w; i++){
52             scanf("%d%d%d"&u, &v, &W);
53             e[el].u = u;
54             e[el].v = v;
55             e[el++].w = -W;
56         }
57         bellman();
58     }
59     return 0;
60 }
61 
62 

posted on 2008-09-04 00:03 memorygarden 阅读(1856) 评论(1)  编辑 收藏 引用 所属分类: 报告

Feedback

# re: poj 3259 Wormholes 2012-05-02 19:44 yc
请问大牛为什么不初始化d数组就能过?  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理