题意描述

Sightseeing Cows G

给定一张有向图，图中每个点都有点权 \(a_i\)，每条边都有边权 \(e_i\)。

求图中一个环，使 “环上个点权之和” 除以 “环上各边权之和” 最大。输出最大值。

解释一下，原题目中并没有点明这是一个环，但是从：

奶牛们不会愿意把同一个建筑物参观两遍。

可以看出，不管怎么走，走环一定是最优的，因为重复走相当于无故增加分母。

算法分析

据说这是一道 0/1 分数规划的题目，但是其实可以用更加通俗易懂的方法来解释。

假设用 \(v_i,e_i(1\leq i\leq k)\) 分别表示环上的点权和边权。

那么显然题目就是要找到最大的 \(\frac{\sum^{k}_{i=1} v_i}{\sum^{k}_{i=1} e_i}\)。

利用二分答案，当 \(\sum^k_{i=1} (mid\times e_i-v_i)<0\) 时：\(mid<\frac{\sum^{k}_{i=1} v_i}{\sum^{k}_{i=1} e_i}\)，令 \(l=mid\)。

反之，当 \(\sum^k_{i=1} (mid\times e_i-v_i)\geq 0\)：\(mid\geq \frac{\sum^{k}_{i=1} v_i}{\sum^{k}_{i=1} e_i}\)，令 \(r=mid\)。

那么就将 \(e(x,y)\) 转化为 \(mid\times e_i-a[x]\)，利用 SPFA 判断是否有负环即可。

代码实现

应为题目不保证图的连通性，所以 SPFA 开始的时候将所有点都入队。

利用二分答案将最优解变为判定即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#define N 10010
#define M 50010
using namespace std;

int n,m,a[N],head[N],cnt=0,sum[N];
bool vis[N];
double dis[N];
struct Edge{
    int nxt,to,val;
}ed[N<<1];

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
    return x*f;
}

void add(int u,int v,int w){
    ed[++cnt].nxt=head[u];
    ed[cnt].to=v,ed[cnt].val=w;
    head[u]=cnt;
    return;
}

bool chck(double mid){
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        dis[i]=0,vis[i]=true,sum[i]=1;
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        vis[u]=false;
        if(++sum[u]>=n) return true;
        for(int i=head[u];i;i=ed[i].nxt){
            int v=ed[i].to;
            double w=ed[i].val;
            if(dis[v]>dis[u]+(double)(mid*w-(double)a[u])){//注意一下 double 与 int
                dis[v]=dis[u]+(double)(mid*w-(double)a[u]);
                if(!vis[v]) q.push(v),vis[v]=true;
            }
        }
    }
    return false;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);
    }
    double l=0.0,r=1000010.0,mid,eps=1e-5;
    while(r-l>eps){
        mid=(l+r)/2;
        if(chck(mid)) l=mid;
        else r=mid;
    }
    printf("%.2lf",l);
    return 0;
}

完结撒花