[文章目录]
Description
给你一个n个点m条边的有向图，询问所有环中最小的边权平均值。
n<=3000 m<=10000
分数规划
等价于收益为a，花费为1的最优比率环问题。
NOTE:
1.spfa判负环可以写dfs式的，极限O(nm)
2.memset(double,0x43,double); 会有精度问题，清为0比较好
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int head[3100],to[101000],nxt[101000],cnt;
double f[101000],now;
void add(int x,int y,double z)
{
to[++cnt]=y; nxt[cnt]=head[x];
head[x]=cnt; f[cnt]=z;
}
bool vis[3100],ok;
double dis[3100];
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i&&!ok;i=nxt[i]) if(dis[to[i]]>dis[x]+f[i]-now)
{
dis[to[i]]=dis[x]+f[i]-now;
if(vis[to[i]]){ok=1; return ;}
dfs(to[i]);
}
vis[x]=0;
}
bool spfa(double x)
{
now=x; ok=0;
memset(dis,0,sizeof dis);
memset(vis,0,sizeof vis);
for(int i=1;i<=n;++i)
{
dfs(i);
if(ok) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
int x,y; double z;
for(int i=1;i<=m;++i)
{
scanf("%d%d%lf",&x,&y,&z);
add(x,y,z);
}
double l=-10000000,r=10000000,mid;
int t=60;
while(t--)
{
mid=(l+r)/2;
if(spfa(mid)) r=mid;
else l=mid;
}
printf("%.8lf\n",(l+r)/2);
return 0;
}