<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
01分数规划(spfa+二分查找)
先介绍一下01分数规划的概念:
假设有$N$个物品,每个物品有两个权值$(a,b)$,在一些限制条件之下,选出其中的一些物品,使得两个权值之和的比值达到最大值(比如$(\Sigma^n_{i=1}a[i]) / (\Sigma^n_{i=1}b[i])$最大)
而求这个最值的方式,一般是直接对其进行二分查找
这个问题中,可以把一个节点$v$和一条以$v$为起点的边看成一个物品,具有的权值为$(f,t)$,其中$f$是节点的点权,$t$是这条边的边权,限制条件就是选出的$k$个“物品”中,$k$条边首尾相连形成回路,$k$个节点不多不少,刚好是这个回路上的所有节点
接下来考虑二分,首先确定上限,由于$f$,$t$的值都不超过1000,那么假设$f$全是1000,$t$全是1,那么比值在此时达到最大,为1000.0,这个就是二分的初始上限$high$,初始下限$low$当然就是0了,对于此区段上的任意一个值limit,如果它能成为最大值,那么小于limit的所有值都是合法的,最后一定能找到一个合法值,小于它的全合法,大于它的全非法,满足二元性,可以二分查找
最后考虑一下$(\Sigma^n_{i=1}f[i]) / (\Sigma^n_{i=1}t[i])$,假设查找到了一个合法的limit,那么必然有$(\Sigma^n_{i=1}f[i]) / (\Sigma^n_{i=1}t[i])>limit$,可以转化为$\Sigma^n_{i=1}(t[i]\*limit-f[i])<0$,将原来的每个点权和边权的对组$(f,t)$变为$(0,t\*limit-f)$,就转化为了死锁(负权回路)检测问题,spfa可以用了
时间复杂度
$O(24\*l\*p)$
$O(l\*p)$是spfa的时间复杂度,24就是二分查找$log_2x$项的真实值,由于长度为1000,_ZERO为$10^{-4}$,区段的实际长度相当于$10^7$,而$2^{24}=16777216$,这里最多会查找24次
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
#include <iomanip>
using namespace std;
const int L = 1e3 + 5, P = 5e3 + 5;
const double _ZERO = 1e-4;
int fin[P], valPoint[L], valEdge[P], last[L], nxt[P], cnt[L], st[L];
double dist[L];
queue<int> q;
int tot = 2, a, b, t, l, p;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//输入图的节点数和边数
cin >> l >> p;
//输入点权
for (int i = 1; i <= l; i++) cin >> valPoint[i];
auto connect = [=](int s, int e, int v)-> void {
fin[tot] = e;
valEdge[tot] = v;
nxt[tot] = last[s];
last[s] = tot++;
};
while (p--) {
//输入边的端点和权值并连接
cin >> a >> b >> t;
connect(a, b, t);
}
//判断点权之和与边权之和的比值能不能等于limit
auto check = [=](double limit)->bool {
fill(st, st + L, 1);
fill(dist, dist + L, 0.0);
fill(cnt, cnt + L, 0);
for (int i = 1; i <= l; i++) q.push(i);
while (!q.empty()) {
int cur = q.front();
q.pop();
st[cur] = 0;
for (int i = last[cur]; i != 0; i = nxt[i]) {
int nx = fin[i];
//将点权与边权(vp,ve)转化为(0,ve * limit - vp),就成为了一个死锁检测问题
double v = valEdge[i] * limit - (valPoint[cur] * 1.0);
if (dist[nx] > dist[cur] + v) {
dist[nx] = dist[cur] + v;
cnt[nx] = cnt[cur] + 1;
if (cnt[nx] >= l) return true;
if (st[nx] == 0) {
st[nx] = 1;
q.push(nx);
}
}
}
}
return false;
};
//浮点数二分查找,_ZERO的数量级比分度需求更小一点
double low = 0.0, high = 1000.0;
//high-low>_ZERO就相当于整数二分查找的low<high
while (high - low > _ZERO) {
double mid = (high + low) / 2;
if (check(mid)) low = mid;
else high = mid;
}
cout << fixed << setprecision(2) << high << endl;
return 0;
}