UVA 11090 - Going in Cycle!! SPFA

题目大意：

给定一个n个点m条边的加权有向图，求平均权值最小的回路。

思路：

用二分法求解。假设答案为mid，只需要判断是否存在平均值小于Mid的回路。怎么判断呢？假设一个包含k条边的回路，回路上各条边的权值为w1,w2……wk，那么平均值小于mid意味着 w1+w2+……wk< k* mid即：

（w1-mid)+(w2-mid)+……(wk-mid)<0

换句话说，只要把图中没一条边a,b的权值w(a,b)变为w(a,b)-mid，在判断图中有没有负权回路。

怎么判断负权回路呢？这就是SPFA的用法了，一个顶点入队列超过n次，就表示有回路。

记住这个不一定是联通的图。所以一开始要把所有的点加入队列。WA找了半天看了别人代码才发现。

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=52; const int INF=100000000; struct edge { int to; double val; int next; }e[MAXN*MAXN]; int head[MAXN],len,n,m; void add(int from,int to,double val) { e[len].to=to; e[len].val=val; e[len].next=head[from]; head[from]=len++; } bool spfa() { double dis[MAXN]; bool vis[MAXN]; int cnt[MAXN]; queue
     
       q; for(int i=1;i<=n;i++) //图可能是非联通的，所以一开始要把全部加入。WA在这里 { dis[i]=INF; vis[i]=true; cnt[i]=1; q.push(i); } while(!q.empty()) { int cur=q.front(); q.pop(); vis[cur]=false; if(cnt[cur] > n) return true; for(int i=head[cur];i!=-1;i=e[i].next) { int id=e[i].to; if(dis[cur] + e[i].val < dis[id]) { dis[id]=dis[cur]+e[i].val; if(!vis[id]) { cnt[id]++; vis[id]=true; q.push(id); } } } } return false; } void change(double x) { for(int k=1;k<=n;k++) for(int i=head[k];i!=-1;i=e[i].next) e[i].val+=x; } bool test(double x) { change(-x); bool ok=spfa(); change(x); return ok; } int main() { int T; scanf(%d,&T); for(int ri=1;ri<=T;ri++) { len=0; memset(head,-1,sizeof(head)); double L=INF,R=0; scanf(%d%d,&n,&m); for(int i=0;i
      
        val) L=val; add(from,to,val); } printf(Case #%d: ,ri); if(!test(R+1)) { printf(No cycle found. ); continue; } while(R-L > 1e-3) //浮点数判断大小要这样 { double mid = L + (R-L)/2; if(test(mid)) R = mid; else L = mid; } printf(%.2lf ,R); } return 0; }