来源:acwing
分析:
题目要求 Σ f i Σ g i \frac{\Sigma{f_i}}{\Sigma{g_i}} ΣgiΣfi的最大值,这种问题称为01分数规划,通俗点说,就是一堆的和除以一堆的和,要求比值最大。
对于本题
我们可以通过二分来做,二分啥呢?就是对于一个环,二分一个mid值,判断是否满足 Σ f i Σ g i ≥ m i d \frac{\Sigma{f_i}}{\Sigma{g_i}} \geq mid ΣgiΣfi≥mid,然后我们就可以来不断更改二分的区间,直到找到 Σ f i Σ g i \frac{\Sigma{f_i}}{\Sigma{g_i}} ΣgiΣfi的最大值。
思路确定了,那么具体如何实现呢?
Σ
f
i
Σ
g
i
≥
m
i
d
\frac{\Sigma{f_i}}{\Sigma{g_i}} \geq mid
ΣgiΣfi≥mid 由于这里的边都是正权边,所以可以移项,变成
Σ
f
i
≥
m
i
d
×
Σ
g
i
{\Sigma{f_i}} \geq mid \times{\Sigma{g_i}}
Σfi≥mid×Σgi
再变一下:
Σ f i − m i d × Σ g i ≥ 0 {\Sigma{f_i}} - mid \times{\Sigma{g_i}} \geq0 Σfi−mid×Σgi≥0
将求和符号提出,亦等价于:
Σ
(
f
i
−
m
i
d
×
g
i
)
≥
0
{\Sigma{(f_i} - mid \times{g_i})} \geq0
Σ(fi−mid×gi)≥0
如下建图:
看完上图,其实我们还能继续推导:
Σ
(
f
i
−
m
i
d
×
g
i
)
≥
0
{\Sigma{(f_i} - mid \times{g_i})} \geq0
Σ(fi−mid×gi)≥0 等价于 图中存在正环
总结一下01分数规划的套路:
由于是求正环,本质上还是求负环,只不过最短路变成最长路。
而且,边权需要自定义,如上图,边权wf[t] - mid * wt[i]
,其中wf[t]
表示t点的点权,wt[i]
表示从t到i的边权,这样合起来作为该边的边权,相当于spfa求最最短路的边权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; // 统计每个点最短路经过的边数 if(cnt[j] >= n) return true; //存在正环
ac代码
#include<bits/stdc++.h> using namespace std; const int N = 1010, M = 5010; int n, m; int wf[N]; // 点权 int h[N], e[M], wt[M], ne[M], idx; // wt[]是边权 bool st[N]; double dist[N]; int cnt[N]; // 统计每个点最短路上边的数量 void add(int a, int b, int c){ e[idx] = b, wt[idx] = c, ne[idx] = h[a], h[a] = idx ++; } // spfa判负环的模板(当然,这里是判正环,本质上是一样的) bool check(double mid){ // 求负环时不需要初始化dist memset(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]; // 求正环,最长路 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; //存在正环 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){ // 经验上来说和保留位数多两位 double mid = (l + r) / 2; if(check(mid)) l = mid; else r = mid; } printf("%.2lf\n", r); }
https://www.acwing.com/problem/content/363/