题面

Bzoj

洛谷

题解（0/1分数规划+spfa）

考虑$0/1$分数规划，设当前枚举到的答案为$ans$

则我们要使（其中$\forall b_i=1$）

$$

\frac{\sum_{i=1}^{ta[e_i]}{\sum_{i=1}}tb[v_i]}< ans

\ \therefore\sum a[e_i]-ans*b[v_i]=\sum a[e_i]-ans<0

$$

则问题就变成了判断图内是否存在一个负环...

时间复杂度:$O(nmlog)$

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::swap; using std::sort;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int N = 3e3 + 10, M = 1e4 + 10;

const double eps = 1e-9;

int n, m, from[N], cnt, to[M], nxt[M]; double dis[M];

inline void addEdge(int u, int v, double w) {

    to[++cnt] = v, nxt[cnt] = from[u], dis[cnt] = w, from[u] = cnt;

}

double p[N]; bool vis[N], flag;

void spfa(int u, double k) {

	vis[u] = 1;

	for(int i = from[u]; i; i = nxt[i]) {

		if(flag) return ;

		int v = to[i]; double w = dis[i] - k;

		if(p[v] > p[u] + w) {

			if(vis[v]) return (void)(flag = 1);

			p[v] = p[u] + w, spfa(v, k);

		}

	}

	vis[u] = 0;

}

int main () {

	read(n), read(m); int u, v; double w;

	for(int i = 1; i <= m; ++i)

		read(u), read(v), scanf("%lf", &w), addEdge(u, v, w);

	double l = -1e7, r = 1e7, ret;

	while(r - l > eps) {

		double mid = l + (r - l) / 2.;

		memset(p, 0, sizeof p), memset(vis, 0, sizeof vis);

		flag = 0;

		for(int i = 1; i <= n; ++i) {

			spfa(i, mid); if(flag) break;

		}

		if(flag) ret = mid, r = mid - eps;

		else l = mid + eps;

	} printf("%.8lf\n", ret);

	return 0;

}

题解（动态规划+结论）

显然，如果真的将渐进复杂度卡满的话（甚至卡到指数级），你是过不去的，这里讲一下这题真正意义上的正解（貌似出这道题的本意就是考察$0/1$分数规划）。

为什么说是结论呢？根据Karp在1977年的论文，他讲述了一种$O(nm)$的算法，用来求有向强连通图中最小平均权值回路，也就是这题的模型。具体可以去看$_rqy$的博客

我们新建一个节点，从它到每个点连一条权值任意的边（比如都是$0$），再令$F_j(i)$表示从新建的点到$i$点恰好经过$j$条边的最短路，那么有

$$

ans=\min_{1\leq i\leq n, F_{n+1}(i)\neq\infty}\max_{j=1}^{n}\left[\frac{F_{n+1}(v)-F_k(v)}{n+1-k}\right]

$$

求$f$可以用动态规划来求，之后就是套公式了。

但是啊，在$Bzoj$上是过不去的，空间只有$64MB$，可以用滚动数组进行优化。