laekov

做过。但是不对。

迷之找负环。

初值直接赋为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);

}