POJ 3259 Wormholes


Bellman_Ford 算法,

利用Bellman_Ford算法判断是否存在负回路。如果存在负回路就一定可以回到(不停的走这个回路,直到赚到的负值够与回去的值抵消的),如果不存在一定不可以回去。
用cin500+ms, 用scanf  100+ms

#include<iostream>
#include
<stdio.h>
using namespace std;
const int INF=0x0fffffff;
struct type
{
       
int s,t;
       
int len;
}edge[
30000];

int n,m,w,nedge=0;
int d[505];
bool Bellman_Ford()
{
     
bool isPossible=false;
     
for(int j=1; j<=n; j++)d[j]=INF;
     d[
1]=0;
     
int u,v;
     
bool f;
     
for(int j=1; j<=n-1; j++)
     {
             f
=0;
             
for(int k=1; k<=nedge; k++)
             {
                     u
=edge[k].s; v=edge[k].t;
                     
if(d[v]>d[u]+edge[k].len)
                                 d[v]
=d[u]+edge[k].len;
                     f
=1;            
             }
             
if(f==0)return false;
     }
  /*前面n-1次循环可以求出无负回路时的最短路径,再来一次如果可以更新就一定有负回路。/*
      
for(int k=1; k<=nedge; k++)
             {
                     u
=edge[k].s; v=edge[k].t;
                     
if(d[v]>d[u]+edge[k].len)
                           {  d[v]
=d[u]+edge[k].len; return 1;}
                                
             }
     
    
// system("pause");
     return 0;
     
}

int main()
{
    
int t;
    cin
>>t;
    
while(t--)
    {
              
int i,j,u,v,value;
              scanf(
"%d %d %d",&n,&m,&w);//cin>>n>>m>>w;
              nedge=0;
              
for(int i=1; i<=m; i++)
              {
                      scanf(
"%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                      ++nedge;
                      edge[nedge].s
=u;
                      edge[nedge].t
=v;
                      edge[nedge].len
=value;
                      
++nedge;
                      edge[nedge].s
=v;
                      edge[nedge].t
=u;
                      edge[nedge].len
=value;
              }     
                  
              
for(int i=1; i<=w; i++)
              {
                      scanf(
"%d %d %d",&u,&v,&value);//cin>>u>>v>>value;
                      ++nedge;
                      edge[nedge].s
=u;
                      edge[nedge].t
=v;
                      edge[nedge].len
=-value;
                      
                     
/* ++nedge;
                      edge[nedge].s=v;
                      edge[nedge].t=u;
                      edge[nedge].len=-value;
                      
*/
              }
              
              
if(Bellman_Ford())
                         cout
<<"YES"<<endl;
              
else       cout<<"NO"<<endl;
     
    }
    system(
"pause");
    
return 0;
}

posted on 2010-08-09 19:38 田兵 阅读(482) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜