spfa 判断负环的话
1.某个点出队n次，存在负环。
2.某条路径上的边数大于等于n,说明存在负环。(通常采用这种)
0 1 分数划分的话(通常配合二分做)
比如 题目求 ∑wf[i] / ∑wt[i] > mid ==> ∑( wf [i] - mid * wt[i] ) > 0 ,那这样就是在求是否存在 正环。
而通常的spfa时判断存不存在负环 那怎么变呢， 第一种 可以把上面 不等式填个负号， 转化成求 负环，第二种 就是 我转变一下思路，假如存在负环，假如 当前这个点是t，它的邻接点是就 j ,dist[j]的更新条件是dist[t]+（wf [i] - mid * wt[i]）< dist[ j ]，那么同样的假如存在正环，我们只要改变一下更新判断的条件， dist[t]+（wf [i] - mid * wt[i]）>dist[ j ] ,我们就更新一下 dist[ j ] 。
这里其实有个trick，就是当数据很多的时候，看更新的点数已经是原来的几十倍的话，就有大概率是环，经验值。
题目的话就是，
AcWing 361
观光奶牛
//0 1分数规划 #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=1010,M=5010; int n,m; int wf[N]; int h[N],e[M],ne[M],wt[M],idx; int q[N],cnt[N]; double dist[N]; bool st[N]; bool check(double mid) { memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); int hh=0,tt=0; for(int i=1;i<=n;++i) { q[tt++]=i; st[i]=true; } while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+wf[t]-mid*wt[i]) { dist[j]=dist[t]+wf[t]-mid*wt[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n) return true; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } return false; } void add(int a,int b ,int c) { e[++idx]=b,ne[idx]=h[a],h[a]=idx,wt[idx]=c; } int main() { cin>>n>>m; for(int i=1;i<=n;++i) scanf("%d",&wf[i]); while(m -- ) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } double l=0,r=1000; while(r-l>1e-4) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2lf",l); return(0); }
AcWing 1165
单词环
（把一个点拆成 一条边 点数就会下降到26*26=676个，然后还要加小trick才能过）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=700,M=1e5+10; int n,m; int q[N],cnt[N]; double dist[N]; int h[N],e[M],ne[M],w[M],idx; bool st[N]; void add(int a,int b,int c) { e[++idx]=b,ne[idx]=h[a],h[a]=idx,w[idx]=c; } bool check(double mid) { memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); int hh=0,tt=0; for(int i=0;i<676;++i) //26*26=676 { q[tt++]=i; st[i]=true; } int count=0; while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];i;i=ne[i]) { int j=e[i]; if(dist[j] < dist[t]+w[i]-mid) { dist[j]=dist[t]+w[i]-mid; cnt[j]=cnt[t]+1; if(++ count > 10000) return true; //trick 经验值 if(cnt[j]>= N) return true; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } return false; } int main() { char str[1010]; while(scanf("%d",&n),n) { idx=0; memset(h,0,sizeof h); for(int i=0;i<n;++i) { scanf("%s",str); int len=strlen(str); int a=(str[0] - ‘a‘) * 26 + str[1] - ‘a‘; int b=(str[len-2] - ‘a‘) * 26 + str[len-1] - ‘a‘; add(a,b,len); } if(!check(0)) puts("No solution"); else{ double l=0,r=1001; while(r-l>1e-4) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2lf\n",l); } } return(0); }