文章目錄

• • • 題目分析
    • 題目鏈接

題目分析

來源：acwing
分析：

題目要求$\frac{\Sigma f_i}{\Sigma g_i}$的最大值，這種問題稱為01分數(shù)規(guī)劃，通俗點說，就是一堆的和除以一堆的和，要求比值最大。

對于本題

我們可以通過二分來做，二分啥呢？就是對于一個環(huán)，二分一個mid值，判斷是否滿足$\frac{\Sigma f_i}{\Sigma g_i}\ge mid$，然后我們就可以來不斷更改二分的區(qū)間，直到找到$\frac{\Sigma f_i}{\Sigma g_i}$的最大值。

思路確定了，那么具體如何實現(xiàn)呢？

$\frac{\Sigma f_i}{\Sigma g_i}\ge mid$ 由于這里的邊都是正權(quán)邊，所以可以移項，變成 $$\Sigma f_i\ge mid\times \Sigma g_i$$
再變一下:

$$\Sigma f_i?mid\times \Sigma g_i\ge 0$$

將求和符號提出，亦等價于：

$$\Sigma (f_i?mid\times g_i)\ge 0$$
如下建圖：

看完上圖，其實我們還能繼續(xù)推導(dǎo)：
$\Sigma (f_i?mid\times g_i)\ge 0$ 等價于 圖中存在正環(huán)
總結(jié)一下01分數(shù)規(guī)劃的套路：

二分一個定值

整理表達式，重新定義邊權(quán)

套用常規(guī)的圖論算法（負環(huán)、最小生成樹等等）

由于是求正環(huán)，本質(zhì)上還是求負環(huán)，只不過最短路變成最長路。

而且，邊權(quán)需要自定義，如上圖，邊權(quán)wf[t] - mid * wt[i]，其中wf[t]表示t點的點權(quán)，wt[i]表示從t到i的邊權(quán)，這樣合起來作為該邊的邊權(quán)，相當于spfa求最最短路的邊權(quán)w[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; // 統(tǒng)計每個點最短路經(jīng)過的邊數(shù)if(cnt[j] >= n) return true; //存在正環(huán)

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 1010, M = 5010; int n, m; int wf[N]; // 點權(quán)int h[N], e[M], wt[M], ne[M], idx; // wt[]是邊權(quán) bool st[N]; double dist[N]; int cnt[N]; // 統(tǒng)計每個點最短路上邊的數(shù)量void add(int a, int b, int c){e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++; }// spfa判負環(huán)的模板(當然，這里是判正環(huán)，本質(zhì)上是一樣的) bool check(double mid){// 求負環(huán)時不需要初始化distmemset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);queue<int> q;// 所有點都入隊for(int i = 1; i <= n; i ++){q.push(i);st[i] = true;}while(q.size()){auto t = q.front();q.pop();st[t] = false;for(int i = h[t]; ~i; i = ne[i]){int j = e[i];// 求正環(huán)，最長路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 true; //存在正環(huán)if(!st[j]){st[j] = true;q.push(j); }}}}return false; }int main(){memset(h, -1, sizeof h);cin >> n >> m;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){ // 經(jīng)驗上來說和保留位數(shù)多兩位double mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}printf("%.2lf\n", r); }

題目鏈接

https://www.acwing.com/problem/content/363/

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的算法提高课-图论-负环-AcWing 361. 观光奶牛:spfa判正环、负环、01分数规划、二分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。