分析:
这道题我们需要二分答案
对于一个二分出来的mid,只需要判断是否存在平均值小于mid的回路
如何判断呢?
假设存在一条回路k1,k2,k3,…kn平均值小于mid
则有:k1+k2+k3+…+kn < mid*n
移向得:k1-mid+k2-mid+…+kn-mid < 0
这样就很明了了,
我们只要把每条边的权值由w(i,j)变成w(i,j)-mid
用Bellman判断有没有负环就好了
tip
Bellman中,一开始需要把所有的点都入队
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const double INF=1e10;
const double eps=1e-10;
int n,m;
int dcmp(double x)
{
if (fabs(x)<eps) return 0;
else if (x>0) return 1;
else return -1;
}
struct node{
int x,y;
double v;
};
struct Bellman{
int n,m;
vector<node> e;
vector<int> G[100];
int pre[100];
double dis[100];
int cnt[100];
bool in[100];
void init(int n)
{
this->n=n;
e.clear();
for (int i=1;i<=n;i++) G[i].clear();
}
void add(int u,int w,double z)
{
e.push_back((node){u,w,z});
m=e.size();
G[u].push_back(m-1);
}
bool fuhuan()
{
for (int i=1;i<=n;i++) dis[i]=INF;
memset(in,0,sizeof(in));
memset(cnt,0,sizeof(cnt));
queue<int> Q;
for (int i=1;i<=n;++i) //每个结点都要入队
{
dis[i] =0;
in[i]=1;
Q.push(i);
}
while (!Q.empty())
{
int now=Q.front(); Q.pop();
in[now]=0;
for (int i=0;i<G[now].size();i++)
{
node way=e[G[now][i]];
if (dcmp(dis[way.y]-dis[now]-way.v)>0)
{
dis[way.y]=dis[now]+way.v;
pre[way.y]=G[now][i];
if (!in[way.y])
{
in[way.y]=1;
Q.push(way.y);
if (++cnt[way.y]>n) return 1;
}
}
}
}
return 0;
}
};
Bellman A;
int pd(double x)
{
for (int i=0;i<A.m;i++)
A.e[i].v-=x;
bool pp=A.fuhuan();
for (int i=0;i<A.m;i++)
A.e[i].v+=x;
return pp;
}
int main()
{
int T;
scanf("%d",&T);
for (int cas=1;cas<=T;cas++)
{
scanf("%d%d",&n,&m);
A.init(n);
int maxx=0;
for (int i=1;i<=m;i++)
{
int u,w,z;
scanf("%d%d%d",&u,&w,&z);
maxx=max(maxx,z);
A.add(u,w,z);
}
printf("Case #%d: ",cas);
if (!pd(maxx+1)) printf("No cycle found.
");
//如果有环,平均权值一定小于maxx+1
else
{
double l=0;
double r=maxx;
double mid;
while (r-l>1e-3)
{
mid=l+(r-l)/2; //二分的时候有一点不同
if (pd(mid))
r=mid;
else l=mid;
}
printf("%.2lf
",l);
}
}
return 0;
}