心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
用BellmanFord求最长路。
以下是我的代码:
#include<iostream>
#include
<string>
#include
<map>
#include
<algorithm>
#include
<cstdio>
using namespace std;
const int kMaxn(37);
struct Edge
{
    
int u,v;
    
double w;
};

int n,m;
Edge e[kMaxn
*kMaxn];

bool BellmanFord(int s)
{
    
double d[kMaxn];
    
for(int i=1;i<=n;i++)
        d[i]
=(i==s?1:0);
    
for(int i=1;i<=n;i++)
        
for(int j=1;j<=m;j++)
        {
            
int u(e[j].u),v(e[j].v);
            
double w(e[j].w);
            d[v]
=max(d[v],d[u]*w);
        }
    
return d[s]>1;
}

int main()
{
    
/*
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    //
*/

    
int T(0);
    
while(cin>>&& n)
    {
        map
<string,int> id;
        
for(int i=1;i<=n;i++)
        {
            
string t;
            cin
>>t;
            id[t]
=i;
        }
        cin
>>m;
        
for(int i=1;i<=m;i++)
        {
            
string t1,t2;
            cin
>>t1>>e[i].w>>t2;
            e[i].u
=id[t1];
            e[i].v
=id[t2];
        }

        
bool success(false);
        
for(int i=1;i<=n;i++)
            
if(BellmanFord(i))
            {
                success
=true;
                
break;
            }

        printf(
"Case %d: ",++T);
        
if(success)
            printf(
"Yes\n");
        
else
            printf(
"No\n");
    }

    
return 0;
}
posted on 2011-07-31 09:47 lee1r 阅读(269) 评论(1)  编辑 收藏 引用 所属分类: 题目分类:图论

FeedBack:
# re: POJ 2240 Arbitrage
2012-05-02 19:35 | skyming
首先:
谢谢你的代码,找到了自己的错误;
第二:
sucess 那里的循环可以去掉吧  回复  更多评论
  

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