本文主要是介绍观光奶牛 （01分数规划、负环），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
01分数规划问题：类似于观光奶牛这个题中的，求的路径上的点权值和与边权值和的商最大最小。
当前问题的推到如下：
该问题其实可以用二分图来解决， 在不断的二分答案中获取符合条件的最大值。然后问题就转化为如何是否存在和为mid的环。
判断路径上点权和与边权和的商，是否大于mid；
因为比权和为正，因此：
移项得：
因为他们单项是对应的，所以两个求和可以进行合并，如下：
至此可以发现，存在环上路径得权值为正数即可，即是否存在正环。
由上可以将问题转化为一个判断是否存在正环的问题，而判断正环则可以通过spfa来进行判断，spfa在走最短路得时候可以判断负环，走最长路得时候可以判断正环。
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define x first
//#define y second
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
const int mod = 1e9 + 7;
const int N = 1e6+ 10;
int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
int n, m;
int o[N];
int h[N], e[N], wf[N], wt[N], ne[N], idx;
bool st[N];
int cnt[N];
double dist[N];inline void add(int a, int b, int c) {e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}int check(double mid) { // 该板子是用vector建的图，时间肯定没有邻接表快。直需要改一下建图方式即可。queue<int> yi;for(int i = 1; i <= n; i ++) // 初始化标记内容，不影响本次计算的时候使用dist[i] = st[i] = cnt[i] = 0;for(int i = 1; i <= n; i ++) { // 加入起点yi.push(i);st[i] = 1;}while(yi.size()) {int t = yi.front();yi.pop();st[t] = 0;for(int i = h[t]; ~i; i = ne[i]) {int j = e[i];if(dist[j] < dist[t] + wf[t] - mid * wt[i]) { dist[j] = dist[t] + wf[t] - mid * wt[i]; // 更新状态cnt[j] = cnt[t] + 1; if(cnt[j] >= n) return 1; // 该图中点大于等于n，则存在环。if(!st[j]) {yi.push(j);st[j] = 1;}}}}return 0;
}inline void sovle() {cin >> n >> m;memset(h, -1, sizeof h);for(int i = 1; i <= n; i ++ ) cin >> wf[i]; // 记录点权值while(m --) { // 建图并且记录边权值int a, b, c;cin >> a >> b >> c;add(a, b, c);}double l = 0, r = 1010;while(r - l > 1e-4) { // 二分获得答案double mid = (l + r) / 2;if(check(mid)) l = mid; else r = mid;}cout << fixed << setprecision(2) << l << endl; // cout输出两位小数，加速流不能使用scanf
}signed main(void) {IOS;int t = 1;
// cin >> t;while(t --) sovle();return 0;
}这篇关于观光奶牛 （01分数规划、负环）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
