| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
代码,bell man ford C++ 卡到1000#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator