由题意得盈利效率为一个分数，故此题为分数规划。

题目中的盈利效率定义为：环路中的收益/花费的时间，给出的数据是两个集市 \((i,j)\) 从 \(i\) 购买和从 \(j\) 卖出分别的价格和从 \(i\) 到 \(j\) 的时间，并不能直接用于求盈利效率，需要预处理。

设 \(g(i,j)\) 为从 \(i\) 点买入，在 \(j\) 点卖出任意商品的最大利润。

在读入价格时预处理出每个 \(g(i,j)\) 。注意这里要枚举 \(i\) 的所有入边与 \(j\) 的所有出边，并将其差取最大值。

for(int i=1;i<=n;++i) for(int j=1;j<=k_;++j) {
    scanf("%lld%lld",&b[i][j],&s[i][j]);
    if(b[i][j]==-1) b[i][j]=inf;
    if(s[i][j]==-1) s[i][j]=0;
    // 对于无法购买的两个集市，将其值改为相减为-inf 的值，以免影响后面的运算
}
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int t=1;t<=k_;++t)
    g[i][j]=max(g[i][j],s[j][t]-b[i][t]);

设 \(d(i,j)\) 为从 \(i\) 到 \(j\) 所用的最短时间，初始化为正无穷，读入所有两个点距离之后进行 floyd 算法求出。 这里用memset(d,0x3f,sizeof(d))的话只有 82pts，血的教训。

for(int i=1;i<=m;++i) {
    int x, y, z; scanf("%lld%lld%lld",&x,&y,&z);
    d[x][y]=z;
}
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(!d[i][j]) d[i][j]=inf;
for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
    if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j];

设计完状态之后，就可以列出盈利效率的式子了。

不难想到，二分一个 \(mid\)，表示盈利效率为 \(mid\)，设 \(i,j\) 为环路上可以相互到达的点 ，\(V\) 为环路点集。

易得下式 \[ \frac{ \sum \limits_{i,j \in V} g(i,j) }{ \sum \limits_{i,j \in V} d(i,j) } \ge mid \]

但是如此并不能直接进行计算，要把它转化为对环的判断。

所以我们设建一张新图，设 \(f(i,j)\) 为新图上的权值。

不难得到 \[ \sum \limits_{i,j \in V} g(i,j) \ge mid \times \sum \limits_{i,j \in V} d(i,j) \]

\[ \sum \limits_{i,j \in V} g(i,j) - mid \times \sum \limits_{i,j \in V} d(i,j) \ge 0 \]

所以我们令 \[ \sum \limits_{i,j \in V} f(i,j)= \sum \limits_{i,j \in V} g(i,j) - mid \times \sum \limits_{i,j \in V} d(i,j) \]

所以 \[ f(i,j)=g(i,j)-mid \times d(i,j) \quad i,j \in V \] 然后跑 \(\text{Floyd}\) 算法，判断有无环并取最大值，再判断最大值是否大于等于 0。

bool check(int x) {
    int ans=-inf;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        if(i==j) f[i][j]=-inf; else f[i][j]=g[i][j]-x*d[i][j];
    for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        f[i][j]=max(f[i][j],f[i][k]+f[k][j]);
    for(int i=1;i<=n;++i) ans=max(ans,f[i][i]);
    // i 到达 i，表示有环。
    // 因为初始 f[i][i] 设置的是-inf 所以不影响答案
    return ans>=0;
}

二分过程。其中初始 \(l=0\)，\(r=\max{\{ g(i,j) \}}\)。

while(l<r) {
	int mid=(l+r+1)/2;
	if(check(mid)) l=mid; else r=mid-1;
}
printf("%lld",l);

几个细节。

• 值域是 \([0,10^9]\)，对题目中的“如果没有任何一条环路可以盈利，则输出 0”并不需要特判。
• 一定要开 long long！
• 因为我们对权的处理，并不需要除法，因此可以完全无视题目中的向下取整。