每周算法：01分数规划
题目链接观光奶牛
题目描述
给定一张 N N N 个点、 M M M 条边的有向图，每个点都有一个权值 p i p_i pi，每条边都有一个权值 w i w_i wi。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
输出这个最大值。
留意：数据保证至少存在一个环。
输入格式
第一行包罗两个整数 N N N 和 M M M。
接下来 N N N 行每行一个整数，表示 p i p_i pi。
再接下来 M M M 行，每行三个整数 a a a， b b b， w [ i ] w w，表示点 a a a 和 b b b 之间存在一条边，边的权值为 w i w_i wi。
输出格式
输出一个数表示结果，生存两位小数。
样例 #1
样例输入 #1
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
样例输出 #1
6.00
提示
【数据范围】
2 ≤ N ≤ 1000 2≤N≤1000 2≤N≤1000,
2 ≤ M ≤ 5000 2≤M≤5000 2≤M≤5000,
1 ≤ p i , w i ≤ 1000 1≤p_i,w_i≤1000 1≤pi,wi≤1000
算法思想
根据题目描述，求的是图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大，不妨设即环上各点的权值之和为 ∑ p i \sum p_i ∑pi，各边的权值之和为 ∑ w i \sum w_i ∑wi，即求 ∑ p i ∑ w i \frac{\sum p_i}{\sum w_i} ∑wi∑pi的最大值。这种办理“最优比率” 的问题，可以利用「01分数规划」。
01分数规划 ：01指取还是不取，分数即所求型式为 a b \frac{a}{b} ba，规划就是选取最好的方案。
01分数规划一般接纳二分答案的方式求解。对于本题来说，即求是否存在 m i d mid mid，使环上各点的权值之和除以环上各边的权值之和大于 m i d mid mid，即 ∑ p i ∑ w i > m i d \frac{\sum p_i}{\sum w_i}>mid ∑wi∑pi>mid，进一步整理可得： ∑ p i − m i d × ∑ w i > 0 \sum p_i-mid\times \sum w_i>0 ∑pi−mid×∑wi>0
其中， p i p_i pi表示节点 i i i的权值，为了方便处理，可以将节点的边权累加到该节点的出边上，那么不等式可以进一步变化为：
∑ ( p i − m i d × w i ) > 0 \sum ({p_i-mid\times w_i})>0 ∑(pi−mid×wi)>0
那么，要判断在包罗环的图中是否存在 m i d mid mid，使环上各点的权值之和除以环上各边的权值之和大于 m i d mid mid，就等价于判断当图中边权为 p i − m i d × w i {p_i-mid\times w_i} pi−mid×wi时，是否存在正权环。
而判断是否存在正权环可以利用「SFPA」算法，基本思想与判断负环稍有不同。判断负环可以参考博主的另一篇文章：每周一算法：负环判断。判断正权环时：
[*]要求最长路，即 d [ v ] < d [ u ] + w d < d + w d<d+w时，更新 v v v点到出发点的最长路；
[*]当 v v v点到出发点的最长路被更新时，累加最长路中包罗的边数，即 c n t [ v ] = c n t [ u ] + 1 cnt=cnt+1 cnt=cnt+1
[*]如果边数 c n t [ v ] > = n cnt>=n cnt>=n，说明图中存在正权环。
算法实现
综合上述，求 ∑ p i ∑ w i \frac{\sum p_i}{\sum w_i} ∑wi∑pi的最大值算法实现如下：
[*]在 [ L , R ] 范围内通过二分查找答案，对于中间结果 m i d mid mid：
[*]利用SPFA算法判断当边权为 p i − m i d × w i p_i-mid\times w_i pi−mid×wi时，图中是否存在正权环
[*]如果存在正权环，则在 [ m i d , R ] 范围继续查找答案
[*]否则不存在正权环，则在 [ L , m i d ] 范围继续查找答案
时间复杂度
本题中的01分数规划在二分答案的过程中，必要用SPFA算法判断正权环，时间复杂度为 O ( k M l o g W ) O(kMlogW) O(kMlogW)，其中 k k k是常数， M M M为边数， W W W为边权之和。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 5005;
int h, e, w, ne, idx;
int n, m;
int p, q, cnt;
double d;
bool st;
void add(int a, int b, int c)// 添加一条边a->b，边权为c
{
e = b, w = c, ne = h, h = idx ++ ;
}
bool check(double mid) //spfa判断是否存在正权环
{
memset(d, 0, sizeof d); //求最长路，初始化为0
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
int hh = 0, tt = 0;
//将所有点加入队列
for(int i = 1; i <= n; i ++) { q = i, st = true; }
while(hh != tt)
{
int u = q;
if(hh == N) hh = 0; //循环队列
st = false;
for(int i = h; ~ i; i = ne)
{
int v = e;
if(d < d + p - mid * w)
{
d = d + p - mid * w;
cnt = cnt + 1;
if(cnt >= n) return true;
if(!st)
{
q = v, st = true;
if(tt == N) tt = 0;
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> p;
memset(h, -1, sizeof h);
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
double L = 0, R = 1e6;
while(R - L > 1e-4)
{
double mid = (L + R) / 2;
if(check(mid)) L = mid;
else R = mid;
}
printf("%.2lf\n", L);
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]