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 |
直接用spfa过嘛,判回路,超过|v|返回#include<iostream> #include <cstring> #include <queue> using namespace std; #define MAXN 102 #define INF 0xffff int N,M,S; double V; float ratio[MAXN][MAXN]; float commisions[MAXN][MAXN]; float map[MAXN][MAXN]; bool spfa() { bool inqueue[MAXN]; int h[MAXN]; float l[MAXN]; fill(inqueue,inqueue+N+1,false); fill(l,l+N+1,0); fill(h,h+N+1,0); queue<int>q; q.push(S); l[S]=V; bool flag=false; while(!q.empty()) { int x=q.front(); q.pop(); inqueue[x]=false; ++h[x]; if(h[x]>N) { flag=true;break;} for(int i=1;i<=N;++i) { if(map[x][i]!=INF && l[i]<(l[x]-commisions[x][i])*ratio[x][i] ) { l[i]=(l[x]-commisions[x][i])*ratio[x][i] ; if(!inqueue[i]) { inqueue[i]=true; q.push(i); } } } } return flag; }; int main() { while(cin>>N>>M>>S>>V) { for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) map[i][j]=INF; for(int i=1;i<=M;++i) { int A,B; cin>>A>>B; cin>>ratio[A][B]>>commisions[A][B]>>ratio[B][A]>>commisions[B][A]; map[A][B]=map[B][A]=0; } if(spfa())cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator