算法提高课-图论-负环-AcWing 361. 观光奶牛:spfa判正环、负环、01分数规划、二分

文章目录

题目分析

算法提高课-图论-负环-AcWing 361. 观光奶牛:spfa判正环、负环、01分数规划、二分
算法提高课-图论-负环-AcWing 361. 观光奶牛:spfa判正环、负环、01分数规划、二分

来源: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
如下建图:
算法提高课-图论-负环-AcWing 361. 观光奶牛:spfa判正环、负环、01分数规划、二分
看完上图,其实我们还能继续推导:
Σ ( f i − m i d × g i ) ≥ 0 {\Sigma{(f_i} - mid \times{g_i})} \geq0 Σ(fi​−mid×gi​)≥0 等价于 图中存在正环
总结一下01分数规划的套路:

  1. 二分一个定值
  2. 整理表达式,重新定义边权
  3. 套用常规的图论算法(负环、最小生成树等等)

由于是求正环,本质上还是求负环,只不过最短路变成最长路。

而且,边权需要自定义,如上图,边权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/

上一篇:动态规划经典代码


下一篇:2021-03-13