361. 观光奶牛（小数二分，spfa判断正环，01分数规划）

361. 观光奶牛 - AcWing题库

给定一张?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

解析：?

所有在图论问题中形如：一堆的和除以一堆的和，求这个结果的最大值的问题，我们称之为“01分数规划”。

一般此类为题我们同有一种通用的做法———二分。

为了方便写二分算法，我们将式子转换成不含出发的式子：sum(f[i])/sum(t[i])>mid==>sum(f[i])-mid*sum(t[i])>0;

我们将点上的权值放到边上那么上述公式就变成了：sum(f[i]-mid*t[i])>0;

每条边的边权就变成了：f[i]-mid*t[i]

问题至此就等价与图中是存在正环，使得sum(f[i]-mid*t[i])>0成立；

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1e3 + 5, M = 5e3 + 5;
int n, m;
int wf[M];
int h[N], e[M], ne[M], wt[M], idx;
double dist[N];
int q[N], vis[N], cnt[N];

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

int check(double u) {
	memset(dist, 0, sizeof dist);
	memset(vis, 0, sizeof vis);
	memset(cnt, 0, sizeof cnt);
	int hh = 0, tt = 0;
	for (int i = 1; i <= n; i++) {
		q[tt++] = i;
		vis[i] = 1;
	}
	while (hh != tt) {
		int t = q[hh++];
		if (hh == N)hh = 0;
		vis[t] = 0;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] < dist[t] + wf[t] - u * wt[i]) {
				dist[j] = dist[t] + wf[t] - u * wt[i];
				cnt[j] = cnt[t] + 1;
				if (cnt[j] >= n)return 1;
				if (!vis[j]) {
					vis[j] = 1;
					q[tt++] = j;
					if (tt == N)tt = 0;
				}
			}
		}
	}
	return 0;
}


int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 1; i <= n; i++)scanf("%d", &wf[i]);
	for (int i = 1, a, b, c; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}

	double l = 0, r = 1e6, mid;
	while (r - l > 1e-4) {
		mid = (l + r) / 2;

		if (check(mid))l = mid;
		else r = mid;
	}
	printf("%.2lf\n", l);
	return 0;
}

?