/* 求平均權值最小的回路。
這裡有有個轉化。W1+W2+...+Wk<k*mid;
二分回路的平均權值mid，將上式轉化為(W1-mid)+(W2-mid)+.......+(Wk-mid)<0;
即用spfa來判斷是否存在負權回路，注意是負權的回路。
不存在的情況為當mid=max(Wi)+1時依然不存在負權回路，則無解。
因為此時mid為可能取到的最大值，此時都不能有負權回路的話，當mid取更小的值時也不會有。*/
[cpp]
#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;
}
#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;
}
