自动搬运

查看原文

来自洛谷，原作者为

	wu3412790 **

搬运于2025-08-24 21:52:35，当前版本为作者最后更新于2020-03-22 07:20:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先这题并不卡精度。二分的时候只二分整数就没有任何问题了。。。

裸分数规划+Folyd, 预处理出任意两点的距离$g[i][j]$，预处理在i点买某个东西到j点卖出的最大获益$earn[i][j]$,然后二分收益r率。把两点的距离重新定义为$w[i][j]=earn[i][j]-r*g[i][j]$。跑个Floyd，然后判断是否 $\max w[i][i]\geq 0$，即是否有正环即可。

#include <iostream>
#define ll long long
using namespace std;
int const N=101,K=1001,L=8;
ll const INF=1e9;
int n,m,t;
ll s[N][K],b[N][K],earn[N][N],g[N][N],f[N][N];
bool find(ll r){	
	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]=earn[i][j]-r*g[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]);
	ll now=-INF;
	for (int i=1;i<=n;i++) now=max(now,f[i][i]);
	return now>=0;
}
ll get(){
	ll l=1,r=1e9;
	while (l<r-1){
		ll mid=(l+r)/2;
		if (find(mid)) l=mid; else r=mid-1;
	}
	if (find(r)) return r;
	if (find(l)) return l;
	return l-1;
}
int main(){
	cin>>n>>m>>t;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=t;j++){
			cin>>b[i][j]>>s[i][j];
			if (b[i][j]==-1) b[i][j]=INF;
			if (s[i][j]==-1) s[i][j]=0;
		}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			for (int k=1;k<=t;k++)
				earn[i][j]=max(earn[i][j],s[j][k]-b[i][k]);
	for (int i=1;i<=m;i++){
		int x,y;
		ll z;
		cin>>x>>y>>z;
		g[x][y]=z;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (!g[i][j]) g[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 (!g[i][j] || g[i][k]+g[k][j]<g[i][j]) g[i][j]=g[i][k]+g[k][j];
	
	cout<<get()<<endl;
	return 0;
}