链接：
#include <stdio.h>
int main()
{
puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/46348771");
}题解：
分数规划Qwq。
然而它卡判点入n次的那种spfa推断负环。
于是有了一种黑科技：
我们从枚举点 i 開始 dfs 。然后扫到点 j 时。保持 i~j 这一条链上的点被标记，然后强行推断再扫一个点 k 时。是否会到这个链上，然后是不是能又一次更新此点 k 与 i 的距离。。。
这个东西是指数级别时间复杂度的。然而却能够过这道题。
代码：
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 3010
#define M 10100
#define eps 1e-8
using namespace std;
double mid;
struct Eli
{
int v,n;
double f,l;
void re(){l=f-mid;}
}e[M];
int head[N],cnt;
inline void add(int u,int v,double l)
{
e[++cnt].v=v;
e[cnt].f=l;
e[cnt].n=head[u];
head[u]=cnt;
}
int n,m;
bool vis[N];
double dist[N];
bool dfs(int x)
{
vis[x]=1;
int i,v;
for(i=head[x];i;i=e[i].n)
{
v=e[i].v;
if(dist[v]>dist[x]+e[i].l)
{
if(vis[v])
{
vis[x]=0;
return 1;
}
else {
dist[v]=dist[x]+e[i].l;
if(dfs(v))
{
vis[x]=0;
return 1;
}
}
}
}
vis[x]=0;
return 0;
}
bool check()
{
memset(dist,0,sizeof dist);
for(int i=1;i<=m;i++)e[i].re();
for(int i=1;i<=n;i++)if(dfs(i))return 1;
return 0;
}
int main()
{
int i,a,b;
double c;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d%lf",&a,&b,&c);
add(a,b,c);
}
double l=-1e7,r=1e7;
for(i=60;i--;)
{
mid=(l+r)/2.0;
if(check())r=mid;
else l=mid;
}
printf("%.8lf\n",l);
return 0;
}