POJ1860 SPFA判断正环

题目大意：给定N种货币，某些货币之间可以相互兑换，现在给定一些兑换规则，问能否从某一种货币开始兑换，经过一些中间货币之后，最后兑换回这种货币，并且得到的钱比之前的多。

思路： 一种货币可以看成一个点。 一个点出发，最后回到自己时反而变大，说明题目中有正环。 所以，只要多设一个数组储存有没有点被松弛n次（即自己也被自己松弛）即可。 简而言之，本体就是判断“负环”。

/* Time:0ms memory:408k */ #include<cstdio> #include<cstring> using namespace std; #define N 105 int n,m,s,vis[N],que[N*N]; double v,dis[N],r[N][N],c[N][N]; bool b[N]; inline bool spfa(){ int hd=1,tl=1; while(hd<=tl) { int x=que[hd++]; b[x]=0; for(int i=1; i<=n; i++) { double k=(dis[x]-c[x][i])*r[x][i]; if(k>dis[i]) { dis[i]=k; if(!b[i]) { que[++tl]=i; b[i]=1; vis[i]++; if(vis[i]==n) return 1; } } } } return 0; } int main() { scanf("%d%d%d%lf",&n,&m,&s,&v); while(m--) { int a,b; scanf("%d%d",&a,&b); scanf("%lf%lf%lf%lf",&r[a][b],&c[a][b],&r[b][a],&c[b][a]); } dis[s]=v; que[1]=s; puts(spfa()?"YES":"NO"); }