做过。但是不对。
迷之找负环。
初值直接赋为0，这样可以节省找没用的最短路的时间。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge {
int t;
double v;
edge *next;
};
const int maxn = 3009;
const int maxm = 10009;
const double eps = 1e-9;
const double finf = 1e20;
int n, m;
bool iq[maxn];
double d[maxn], ave;
edge *ep, *head[maxn], elst[maxm];
bool dfs(int p) {
iq[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (d[e-> t] - (d[p] + e-> v) > eps) {
if (iq[e-> t])
return 1;
else {
d[e-> t] = d[p] + e-> v;
if (dfs(e-> t))
return 1;
}
}
iq[p] = 0;
return 0;
}
bool findNagLoop(double ave) {
for (int i = 1; i <= n; ++ i)
d[i] = 0;
for (int i = 0; i < m; ++ i)
elst[i]. v -= ave;
memset(iq, 0, sizeof(iq));
bool res = 0;
for (int i = 1; i <= n && !res; ++ i)
res |= dfs(i);
for (int i = 0; i < m; ++ i)
elst[i]. v += ave;
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
double l = 0, r = 0;
memset(head, 0, sizeof(head));
ep = elst;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++ i) {
int u, v;
double w;
scanf("%d%d%lf", &u, &v, &w);
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
l = min(l, w);
r = max(r, w);
}
while (l + eps < r) {
double mid = (l + r) / 2.0;
if (findNagLoop(mid))
r = mid;
else
l = mid;
}
printf("%.8lf\n", l);
}