0/1分数规划

0/1分数规划是一项不常用到的（但还蛮实用的）算法，一般来讲就是求一个最优比率。

分数规划的简单介绍

  分数规划顾名思义就是求一个分数表达式的最大（小）值。

  比如说有 n 个物品，每个物品有两个权值 a 和 b ，然后让你选出任意件数（但可能会有限制）的物品，使得两个权值和间的比值最大，即求

$$\frac{\sum_{i=1}^{k} a[i]}{\sum_{j=1}^{k} b[j]}$$

（在这里 1~k为挑出的 k 件物品）的最大值，然后对选择物品方面给出一定的限制条件，那么一道0/1 分数规划的题目就完成了。

分数规划的求解方法

  分数规划有两种求解方法，一种是二分法，而另一种则是 Dinkelbach 算法，一般来讲我们选用第一种方法进行分数规划求解。

二分法

  问题同上，求$\frac{\sum_{i=1}^{k} a[i]}{\sum_{j=1}^{k} b[j]}$的最大值，然后加上一个限制：k >= W
  我们令

$$\text { sum }=\sum_{i=1}^{k} a[i], \text { tot }=\sum_{j=1}^{k} b[j], k>=W$$

  然后假设问题中的最优解为 ans ，那么必然有:

$$\frac{\text { sum }}{\text { tot }}<=a n s$$

  移项得：

$$\text { sum }<=\text { ans } \times \text { tot }$$

  继续移就得到：

$$\text { sum }-\text { ans } \times \text { tot }<=0$$

  这样转化有什么用呢？那我们尝试将 sum 和 tot 带回去，就可以得到这么一个式子：

$$\sum_{i=1}^{k}(a[i]-b[i] \times a n s)<=0$$

  这个式子不难理解，就是把整体的贡献转化为了单件物品的贡献。

  那么我们只需要二分这个 ans， 计算出每件物品的a - b * ans，然后排个序，贪心取前 W 个加起来，看看最后的值是否 <=0 ，然后就可以根据结果移动左右边界了。

分数规划的有机结合

  分数规划一般来讲不会单独出现，一般来讲有以下几种形式：

例题：

《观光奶牛》
给定一张 L 个点、P 条边的有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意：数据保证至少存在一个环。

输入格式
第一行包含两个整数 L 和 P。

接下来 L 行每行一个整数，表示 f[i]。

再接下来 P 行，每行三个整数 a，b，t[i]，表示点 a 和 b 之间存在一条边，边的权值为 t[i]。

输出格式
输出一个数表示结果，保留两位小数。

数据范围

2 ≤ L ≤ 1000,
2 ≤ P ≤ 5000,
1 ≤ f[i], t[i] ≤ 1000

输入样例：

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

输出样例：

6.00

AC代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 10010;
const double eps = 1e-4;
int h[N], e[M], ne[M], w[M], idx;
double dist[N];
int cnt[N];
bool st[N];
int f[N], t[N];
int q[N], hh, tt;
int n, m;

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

//spfa判断负环 
bool check(double x){
	memset(dist, 0x3f, sizeof dist);
	memset(cnt, 0, sizeof cnt);
	memset(st, 0, sizeof st);
	hh = 0, tt = 0;
	for(int i = 1; i <= n; i++){
		q[tt++] = i;
		st[i] = true;
	}
	while(hh != tt){
		auto t = q[hh++];
		if(hh == N) hh = 0;
		st[t] = false;
		for(int i = h[t]; ~i; i = ne[i]){
			int j = e[i];
			if(dist[j] > dist[t] + w[i] * x - f[t]){
				dist[j] = dist[t] + w[i] * x - f[t];
				cnt[j] = cnt[t] + 1;
				if(cnt[j] >= n) return true;
				if(!st[j]){
					st[j] = true;
					q[tt++] = j;
					if(tt == N) tt = 0;
				}
			}
		}
	}
	return false;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &f[i]);
	memset(h, -1, sizeof h);
	while(m -- ){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	double l = 0, r = 1000;
	while(r - l > eps){
		double mid = l + (r - l) / 2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	printf("%.2lf\n", l);
	
	return 0;
}