题目链接：

　　题目大意就是判断一个有向图中的是否存在正权环。利用Bellman-ford判断负环的思想，改为求最长路，如果在n-1次后再来一次bellman，如果还能更新，那么就是存在正权环。

SPFA：

1 //STATUS:G++_AC_0MS_728KB 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 #include
             
              11 #include
              
               12 using namespace std;13 #define LL __int6414 #define pii pair
               
                15 #define Max(a,b) ((a)>(b)?(a):(b))16 #define Min(a,b) ((a)<(b)?(a):(b))17 #define mem(a,b) memset(a,b,sizeof(a))18 #define lson l,mid,rt<<119 #define rson mid+1,r,rt<<1|120 const int N=110,INF=0x3f3f3f3f,MOD=1999997;21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;22 23 struct Edge{24 int u,v;25 double r,s;26 }e[N*N];27 28 double d[N];29 double v;30 int first[N],next[N*N],inq[N],cou[N];31 int n,m,s,mt;32 33 void adde(int a,int b,double r,double s)34 {35 e[mt].u=a,e[mt].v=b;36 e[mt].r=r,e[mt].s=s;37 next[mt]=first[a],first[a]=mt++;38 }39 40 int spfa()41 {42 int x,i;43 double t;44 queue
                
                  q;45 mem(inq,0);mem(cou,0);46 for(i=1;i<=n;i++)d[i]=-1;47 d[s]=v;48 cou[s]=1;49 q.push(s);50 while(!q.empty())51 {52 x=q.front();q.pop();53 inq[x]=0;54 for(i=first[x];i!=-1;i=next[i]){55 t=(d[x]-e[i].s)*e[i].r;56 if(t>=0 && t>d[e[i].v]){57 d[e[i].v]=t;58 if(!inq[e[i].v]){59 if(++cou[e[i].v]>=n)return 1;60 inq[e[i].v]=1;61 q.push(e[i].v);62 }63 }64 }65 }66 return 0;67 }68 69 int main()70 {71 // freopen("in.txt","r",stdin);72 int i,j,a,b;73 double r1,s1,r2,s2;74 while(~scanf("%d%d%d%lf",&n,&m,&s,&v))75 {76 mt=0;77 mem(first,-1);78 for(i=0;i