传送门
题意：给定起始拥有货币种类为s，拥有数量为v。现有n种不同货币，m种货币转换。货币转换为双向，但两种转换汇率r和手续费c不同。询问是否能够换一圈，最后s的数目增长。（问能否钱从天上来
解：由于要求换一圈货币种类仍为s，所以要求有环。由于不能亏，所以要求是正环。spfa找环即可。
注：spfa找正环temp>dis[to]，找负环temp
代码：
#include
#include
#include
using namespace std;
#define ll long long
#define maxx 105
#define inf 0x7fffffff
//#define int long long
int n,m,s;
double v;
struct edge{
int u,v;
double r,c;
int nxt;
}e[maxx*2];
int head[maxx]={0},cnt=0;
void add(int u,int v,double r,double c){
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].r=r;
e[cnt].c=c;
e[cnt].nxt=head[u];
head[u]=cnt;
}
double dis[maxx];
int vis[maxx]={0},in[maxx]={0};
int spfa(int x){
for(int i=1;i<=n;i++)
dis[i]=0;
queue<int> q;
q.push(x);
vis[x]=1;dis[x]=v;in[x]++;
while(!q.empty()){
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i;i=e[i].nxt){
int to=e[i].v;
double f=(dis[now]-e[i].c)*e[i].r;
if(f>dis[to]){
dis[to]=f;
in[to]++;
if(in[to]>=n)
return 1;
if(!vis[to]){
vis[to]=1;
q.push(to);
}
}
}
}
return 0;
}
signed main() {
scanf("%d%d%d%lf",&n,&m,&s,&v);
for(int i=0;i){
int x,y;
double r1,c1,r2,c2;
scanf("%d%d%lf%lf%lf%lf",&x,&y,&r1,&c1,&r2,&c2);
add(x,y,r1,c1);
add(y,x,r2,c2);
}
if(spfa(s))
printf("YES\n");
else
printf("NO\n");
return 0;
}
//poj也没有万能头qaq
//但是vj上有中文版本就又快乐起来了