UVA11090 Going in Cycle!!（二分判负环）

UVA11090 Going in Cycle!!

二分答案，用spfa判负环。

注意格式；图不一定连通。

复杂度$O(nmlog(maxw-minw))$

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<cmath>

 #define re register

 using namespace std;

 typedef double db;

 const db eps=1e-;

 #define N 100

 #define M 20000

 int n,m,t,ri[N]; db d[N],val[M<<]; bool inh[N],vis[N];

 int cnt,hd[M],nxt[M<<],ed[M],poi[M];

 void adde(int x,int y,db v){

     nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt;

     ed[x]=cnt; poi[cnt]=y; val[cnt]=v;

 }

 bool spfa(int st,db lim){

     memset(d,,sizeof(d));

     memset(inh,,sizeof(inh));

     memset(ri,,sizeof(ri));

     queue<int> h; h.push(st);

     inh[st]=; d[st]=; vis[st]=;

     while(!h.empty()){

         int x=h.front(); h.pop();

         inh[x]=;

         for(int i=hd[x];i;i=nxt[i]){

             int to=poi[i];

             if(d[x]+val[i]-lim<d[to]){

                 d[to]=d[x]+val[i]-lim;

                 ri[to]=ri[x]+; vis[to]=;

                 if(ri[to]>=n) return ;//出现次数>=n则有环

                 if(!inh[to])

                     inh[to]=,h.push(to);

             }

         }

     }return ;

 }

 bool check(db lim){

     memset(vis,,sizeof(vis));

     bool ok=;

     for(re int i=;i<=n&&!ok;++i)

         if(!vis[i]) ok|=spfa(i,lim);

     return ok;

 }

 int main(){

     scanf("%d",&t); int q1,q2;db q3;

     for(int w=;w<=t;++w){

         memset(hd,,sizeof(hd)); cnt=;

         memset(nxt,,sizeof(nxt));

         memset(ed,,sizeof(ed));

         scanf("%d%d",&n,&m);

         db l=1e8,r=-1e8;

         for(re int i=;i<=m;++i){

             scanf("%d%d%lf",&q1,&q2,&q3);

             adde(q1,q2,q3);

             l=min(q3,l);

             r=max(q3,r);

         }printf("Case #%d: ",w);

         if(!check(r+))//如果减去最大边+1仍无负环，这个图就是无环图

             {printf("No cycle found.\n"); continue;}

         while(fabs(r-l)>eps){//二分

             db mid=(l+r)/2.0;

             if(check(mid)) r=mid;

             else l=mid;

         }printf("%.2lf\n",l);

     }return ;

 }