https://www.lydsy.com/JudgeOnline/problem.php?id=4898
https://www.lydsy.com/JudgeOnline/problem.php?id=5367
https://www.luogu.org/problemnew/show/P3778
将如此之长的题面读完之后，你惊奇的发现，这题竟然是一道水题！
（虽然水但是我竟然发现我floyd和spfa都能写错我可能是OI之耻吧……）
那些乱七八糟的货物倒卖实际上可以总结为i~j，我倒卖的最大价值为w权，我经过的最短时间为t权，求sigma(w)/sigma(t)的最大值。
这明显是0/1分数规划套路，二分答案然后找正环就行了（不敢找负环怕爆ll……不知道可不可行。）
当然别忘了对于没法到达的(i,j)，其不存在边，如果你用邻接矩阵的话，记的用什么方法判掉这些边。
（另外自己不能向自己倒卖商品）
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
const int K=;
const int INF=1e9;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
int n,m,k;
int b[N][K],s[N][K],tim[N][N],cas[N][N],inq[N];
ll dis[N][N],big[N];
bool vis[N];
queue<int>q;
bool spfa(){
while(!q.empty())q.pop();
for(int i=;i<=n;i++)big[i]=vis[i]=inq[i]=;
for(int i=;i<=n;i++)q.push(i),vis[i]=inq[i]=;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=;
for(int v=;v<=n;v++){
if(big[v]-dis[u][v]<=big[u]){
big[v]=big[u]+dis[u][v];
if(!vis[v]){
inq[v]++;vis[v]=;
if(inq[v]>n)return ;
q.push(v);
}
}
}
}
return ;
}
inline bool pan(int w){
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dis[i][j]=(ll)cas[i][j]-(ll)w*tim[i][j];
return spfa();
}
int erfen(int l,int r){
while(l<r){
int mid=(l+r+)>>;
if(pan(mid))l=mid;
else r=mid-;
}
return l;
}
int main(){
n=read(),m=read(),k=read();
for(int i=;i<=n;i++){
for(int j=;j<=k;j++){
b[i][j]=read(),s[i][j]=read();
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++)
tim[i][j]=INF,cas[i][j]=-INF;
tim[i][i]=;
}
for(int i=;i<=m;i++){
int u=read(),v=read(),w=read();
tim[u][v]=min(tim[u][v],w);
}
for(int l=;l<=n;l++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(tim[i][j]-tim[i][l]>tim[l][j])
tim[i][j]=tim[i][l]+tim[l][j];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(i!=j&&tim[i][j]!=INF){
cas[i][j]=;
for(int l=;l<=k;l++)
if(b[i][l]>=&&s[j][l]>=&&b[i][l]<s[j][l])
cas[i][j]=max(cas[i][j],s[j][l]-b[i][l]);
}
printf("%d\n",erfen(,INF));
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++