Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

代码,bell man ford C++ 卡到1000

Posted by hzl88888888 at 2012-07-04 16:17:47 on Problem 1860
#include <cstdio>
#include <cstdlib>

struct record 
{
       float huil,yongj;
       };
       
int n,m,s,i,j,k,change1,change2;
float rab,cab,rba,cba,v,w[200];
struct record pay[200][200];

void bellmanford()
{   bool change;
    int i,j,k;
    w[s]=v;
    for (i=1;i<=n;i++)
      if (pay[s][i].huil!=0) {w[i]=(w[s]-pay[s][i].yongj)*pay[s][i].huil;
                              if (w[i]<0) w[i]=0;
                             }
      k=0;
    do 
    {change=false;k++;
    if (k>1000) break;
    for (j=1;j<=n;j++)
      for (i=1;i<=n;i++)
        if (w[i]!=0&&pay[i][j].huil!=0&&(w[i]-pay[i][j].yongj)*pay[i][j].huil>w[j])
          {
          change=true;
          w[j]=(w[i]-pay[i][j].yongj)*pay[i][j].huil;
          if (j==s) {printf("YES");
                     exit(0);
                    }
          if (w[j]<0) {
                      printf("NO");
                      exit(0);
                      }
          }
     }
     while (change=true);
     printf("NO\n");
}

int main()
{   freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scanf("%d%d%d%f",&n,&m,&s,&v);
    for (i=1;i<=m;i++)
      {
      scanf("%d%d%f%f%f%f",&change1,&change2,&rab,&cab,&rba,&cba);
      pay[change1][change2].huil=rab;pay[change1][change2].yongj=cab;
      pay[change2][change1].huil=rba;pay[change2][change1].yongj=cba;
      }
  bellmanford();
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator