[URAL 1162] 判断正环

【题目大意】给定N个货币和M种兑换方式，问能否不断加钱？

【算法分析】用spfa算法判断有无正权回路。如果一个点进入队列超过N次。。。那就是有正权了。

【其它】注意精度要控制一下

【code】

#include #include #include #include using namespace std;
struct gtp{int x,y,next;double rate,sui;}g[201];
double d[101],sm;
int v[101],list[101],n,e,st,ls[101],insnum[101];

inline void addedge(int x,int y,double rate,double sui){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
       g[e].rate=rate; g[e].sui=sui;
}

void init(){
     int m; e=0;
     scanf("%d%d%d%lf",&n,&m,&st,&sm);
     for (int i=1;i<=m;i++){
         double rate,sui;
         int xx,yy;
         scanf("%d%d%lf%lf",&xx,&yy,&rate,&sui);
         addedge(xx,yy,rate,sui);
         scanf("%lf%lf",&rate,&sui);
         addedge(yy,xx,rate,sui);
     }
}

bool spfa(){
     memset(d,0,sizeof(d));
     memset(v,0,sizeof(v));
     memset(insnum,0,sizeof(insnum));
     v[st]=1; d[st]=sm; insnum[st]=1; list[0]=st;
     int head=-1,tail=0;
     while (head!=tail){
           head++; if (head>100) head=0;
           for (int t=ls[list[head]];t!=0;t=g[t].next)
             if ((d[g[t].x]-g[t].sui)*g[t].rate>=d[g[t].y]+1e-6){
               d[g[t].y]=(d[g[t].x]-g[t].sui)*g[t].rate;
               if (v[g[t].y]==0){
                 v[g[t].y]=1;
                 tail++; if (tail>100) tail=0;
                 list[tail]=g[t].y;
                 insnum[g[t].y]++;
                 if (insnum[g[t].y]>n) return true;
               }
             }
           v[list[head]]=0;
     }
     return false;
}

int main(){
    init();
    if (spfa()) printf("YESn");
           else printf("NOn");
}