| ||||||||||
| 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