題目大意：給定N種貨幣，某些貨幣之間可以相互兌換，現在給定一些兌換規則，問能否從某一種貨幣開始兌換，經過一些中間貨幣之后，最后兌換回這種貨幣，并且得到的錢比之前的多。
思路： 一種貨幣可以看成一個點。 一個點出發，最后回到自己時反而變大，說明題目中有正環。 所以，只要多設一個數組儲存有沒有點被松弛n次（即自己也被自己松弛）即可。 簡而言之，本體就是判斷“負環”。
/* Time:0ms memory:408k*/#include<cstdio>#include<cstring>using namespace std;#define N 105int 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");}新聞熱點
疑難解答
