POJ 1860 C++ （圖論）

//知道了什么是bellman_ford;
//一定要堅持下去
#include<iostream>
#define eps 1e-8
using namespace std;
typedef struct E{
int v,u;
double r,c;
};
int n,m,s,num;
double money,d[101];
E e[201];
bool  bellman()
{ int flag;
  memset(d,0,sizeof(d));
  d[s]=money;
  while(d[s]<=money+eps)
      { flag=0;
        for(int i=0;i<num;i++)
            if(d[e[i].v]+eps<(d[e[i].u]-e[i].c) * e[i].r)
              { d[e[i].v]=(d[e[i].u]-e[i].c)*e[i].r;
                flag=1;
               }

           if(!flag)
                 return d[s]>money+eps;
         }
     return true;          
}

int main()
{int V,U;
double cv,rv,cu,ru;
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
  while((scanf("%d%d%d%lf",&n,&m,&s,&money))!=EOF)
     {num=0;
     for(int i=1;i<=m;i++)
          {scanf("%d%d%lf%lf%lf%lf",&U,&V,&rv,&cv,&ru,&cu);
            e[num].v=V;
            e[num].u=U;
            e[num].r=rv;
            e[num++].c=cv;
            e[num].v=U;
            e[num].u=V;
            e[num].r=ru;
            e[num++].c=cu;
           }
       if(bellman())
          printf("YES\n");
       else
          printf("NO\n");
      }

      return 0;
}            

posted on 2008-11-27 00:15 蝸牛 閱讀(1668) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC