洛谷P2868 [USACO07DEC]Sightseeing Cows G 题解

题目链接：P2868 [USACO07DEC]Sightseeing Cows G

题意：

给定有向图，有点权 \(F_i\) 和边权 \(T_i\) ，找一条回路（不一定是简单回路），使得 \[ \dfrac{\sum F_i}{\sum T_i} \] 尽可能的大，求出这个值

若回路的结点序列中含相同结点，只计算一次点权

\(2 \le n \le 10^3,1\le m \le 5 \times 10^3,1 \le F_i,T_i \le 10^3\)

比较经典的01分数规划问题

设 \[ \sum F_i \times \dfrac{1}{\sum T_i} > x \] 移项可得 \[ \sum (F_i - x T_i) > 0 \] 取个反可得 \[ \sum (xT_i - F_i) < 0 \] 然后就变成了判负环的问题。

二分一个 \(x\) ，然后每次跑个spfa检验一下

时间复杂度 \(O(\log_2 10^7 \times nm)\)

为什么大于也可以求出答案呢？因为当 \(x\) 足够精确时，也就是答案了

这里有个问题，题目说的是回路，不是环（简单回路），

不过事实上答案中都是环（简单回路）

这里有个证明，比较繁琐，因此我来提供一种简单证明

---

证：考虑最简单的情况，

设两个环 \(A,B\) 的交集为结点 \(u\) （此时图可以是一个8字形）

设 \(A\) 的答案是 \(x\) ，\(B\) 的答案是 \(y\)

• 若 \(x=y\) ，

  则若合并 \(A,B\) ，多出来的几条连接 \(u\) 的边会使分母增加

  则答案小于 \(x\)

  只有这几条边的 \(T_i\) 都为 \(0\) 时，

  合并后的答案才能达到 \(x\) ，但是数据范围里没有这种情况。

  故合并 \(A,B\) 一定不是最优的。

• 若 \(x>y\) 或 \(x<y\)

  那显然合并了就更烂了哇。肯定不是最优的。

证毕。

---

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)
#define M (int)(5e3+15)
struct Edge
{
    int u,v,T,next;
}e[M];
int n,m,F[N];
double d[N];
int head[N],pos=1,vis[N],cnt[N];
void addEdge(int u,int v,int T)
{
    e[++pos]={u,v,T,head[u]};
    head[u]=pos;
}
queue<int> q;
bool spfa(int st,double x)
{
    while(!q.empty())q.pop();
    q.push(st);vis[st]=1;d[st]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            double w=x*e[i].T-F[u];
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                if(!vis[v])
                {
                    q.push(v);++cnt[v];vis[v]=1;
                    if(cnt[v]>=n)return 1;
                }
            }
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> F[i];
    for(int i=1,u,v,T; i<=m; i++)
    {
        cin >> u >> v >> T;
        addEdge(u,v,T);
    }
    double l=0,r=1005;
    while(fabs(r-l)>1e-4)
    {
        double mid=(l+r)/2;
        bool ok=0;
        for(int i=1; i<=n; i++)
        {
            d[i]=1e66;
            cnt[i]=vis[i]=0;
        }
        for(int i=1; i<=n; i++)
        {
            if(!cnt[i])
            {
                if(spfa(i,mid))
                    {ok=1;break;}
            }
        }
        ok?l=mid:r=mid;
    }
    cout << fixed << setprecision(2);
    cout << l << '\n';
    return 0;
}