学步园

/* 求平均权值最小的回路。

这里有有个转化。W1+W2+...+Wk<k*mid;

二分回路的平均权值mid，将上式转化为(W1-mid)+(W2-mid)+.......+(Wk-mid)<0;

即用spfa来判断是否存在负权回路，注意是负权的回路。

不存在的情况为当mid=max(Wi)+1时依然不存在负权回路，则无解。

因为此时mid为可能取到的最大值，此时都不能有负权回路的话，当mid取更小的值时也不会有。*/

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxm=3001;
const int maxn=51;
struct edge
{
    int next,to;
    double w;
} e[maxm];
int t;
bool vis[maxn];
int head[maxn],num[maxn];
double d[maxn];
void add(int i,int j,double w)
{
    e[t].to=j;
    e[t].w=w;
    e[t].next=head[i];
    head[i]=t++;
}
int n,m;
bool spfa()
{
    queue <int> q;
    memset(num,0,sizeof(num));
    memset(vis,false,sizeof(vis));
    memset(d,0x7f,sizeof(d));
    for(int i=1; i<=n; i++) vis[i]=true,d[i]=0,q.push(i);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=head[u]; i!=-1; i=e[i].next)
        {
            int v=e[i].to;
            if(d[u]+e[i].w<d[v])
            {
                d[v]=d[u]+e[i].w;
                if(!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                    if(++num[v]>n) return true;
                }
            }
        }
    }
    return false;
}
bool work(double x)
{
    for(int i=0; i<m; i++)
        e[i].w-=x;
    bool ret=spfa();
    for(int i=0; i<m; i++)
        e[i].w+=x;
    return ret;
}
int main()
{
    //freopen("b.txt","r",stdin);
    int T,a,b,test=1;
    double w;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        double temp=0;
        t=0;
        memset(head,-1,sizeof(head));
        for(int i=0; i<m; i++)
        {
            scanf("%d %d %lf",&a,&b,&w);
            add(a,b,w);
            temp=max(temp,w);
        }
        printf("Case #%d: ",test++);
        if(!work(temp+1))
        {
            printf("No cycle found.\n");
            continue;
        }
        double l=0,r=temp,mid;
        while(r-l>1e-3)
        {
            mid=(l+r)/2;
            if(work(mid)) r=mid;
            else l=mid;
        }
        printf("%.2lf\n",l);
    }
    return 0;
}