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