uva11090（spfa判负环）

题目连接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2031

自己没想出，其实也不难。

首先判断图中是否存在环，若不存在则No cycle found.

若存在：

可知lowest mean的范围是介于最大权和最小权之间的。

可以二分，查找符合条件的最小值。

mid满足的条件是，存在k条边，使得w1+w2+w3+……+wk<k*mid;

上式可变形为（w1-mid）+(w2-mid))+……+（wk-mid）<0; 即判断负环。

开始只判断了从1开始是否存在负环,WA几次才意识到问题，负环可能不含点1。。

虚拟一个结点0，到各个点距离为0. 从节点0开始入队即可查找全图是否存在负环。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const double eps=1e-8;
  8 const int inf=0x3f3f3f3f;
  9 const int maxn=110;
 10 
 11 struct edge
 12 {
 13     int v,nex;
 14     double w;
 15 }e[maxn*maxn];
 16 
 17 int head[maxn],cnt=0;
 18 int inq[maxn],vis[maxn];
 19 double dis[maxn];
 20 int n,m;
 21 
 22 void add(int u,int v,double w)
 23 {
 24     e[cnt].v=v;
 25     e[cnt].w=w;
 26     e[cnt].nex=head[u];
 27     head[u]=cnt++;
 28 }
 29 int spfa()
 30 {
 31     queue<int> q;
 32     for(int i=1;i<=n;i++) //虚拟节点0
 33     {
 34         dis[i]=0;
 35         vis[i]=1;
 36         inq[i]=1;
 37         q.push(i);
 38     }
 39     while(!q.empty())
 40     {
 41         int u=q.front();
 42         q.pop();
 43         inq[u]=0;
 44         for(int i=head[u];i!=-1;i=e[i].nex)
 45         {
 46             int v=e[i].v;
 47             if(dis[v]>dis[u]+e[i].w)
 48             {
 49                 dis[v]=dis[u]+e[i].w;
 50                 if(!inq[v])
 51                 {
 52                     inq[v]=1;
 53                     vis[v]++;
 54                     if(vis[v]>n) return 1;
 55                     q.push(v);
 56                 }
 57             }
 58         }
 59     }
 60     return 0;
 61 }
 62 int check(double x)
 63 {
 64     int ok=0;
 65     for(int i=0;i<cnt;i++)
 66         e[i].w-=x;
 67     if(spfa()) ok=1;
 68     for(int i=0;i<cnt;i++)
 69         e[i].w+=x;
 70     return ok;
 71 }
 72 int main()
 73 {
 74     int t;
 75     scanf("%d",&t);
 76     for(int c=1;c<=t;c++)
 77     {
 78         int u,v;
 79         double w,L=inf,R=0;
 80         memset(head,-1,sizeof(head));
 81         cnt=0;
 82         scanf("%d%d",&n,&m);
 83         for(int i=0;i<m;i++)
 84         {
 85             scanf("%d%d%lf",&u,&v,&w);
 86             add(u,v,w);
 87             L=min(L,w);
 88             R=max(R,w);
 89         }
 90         printf("Case #%d: ",c);
 91         if(!check(1+R))
 92             puts("No cycle found.");
 93         else
 94         {
 95             while(R-L>eps)
 96             {
 97                 double mid=L+(R-L)/2;
 98                 if(check(mid)) R=mid;
 99                 else L=mid;
100             }
101             printf("%.2lf
",R);
102         }
103     }
104     return 0;
105 }