题目：https://www.luogu.org/problemnew/show/P3778
转化有点技巧；
其实直接关注比率的上下两项，也就是盈利和时间；
通过暴枚和 floyd 可以处理出两两点间的最大盈利和最小时间，就不用再去关注原图了；
然后就是裸的01分数规划，枚举 ans ，连完全图，判断正环，若有则答案可行；
注意SPFA里一开始把每个点都入队；还要注意0环，代表此时正好是 ans；
WA了十几遍只因为读入优化少写了一个等号...
细节真令人心碎...50个点，错那么一个两个的...
改成 int ，只把SPFA里的 dis 设成 long long ，就A了...为什么全 long long 就不行啊...
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; typedef long long ll; queue<int>q; int const maxn=105,maxk=1005,inf=0x3f3f3f3f; int map[maxn][maxn],val[maxn][maxn],l,r,ans,len[maxn],b[maxn][maxk],s[maxn][maxk]; int n,m,K; ll dis[maxn]; bool vis[maxn]; int rd() { int ret=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return ret*f; } bool pd(int nw) { while(q.size())q.pop(); for(int i=1;i<=n;i++)q.push(i),dis[i]=0,vis[i]=len[i]=1;//每个点入队 while(q.size()) { int x=q.front(); q.pop(); vis[x]=0; for(int u=1;u<=n;u++) if(dis[u]<=dis[x]+(ll)val[x][u]-(ll)nw*map[x][u])//0环 { dis[u]=dis[x]+(ll)val[x][u]-(ll)nw*map[x][u]; if(!vis[u])vis[u]=1,q.push(u),len[u]++; // len[u]=len[x]+1; // if(!vis[u])vis[u]=1,q.push(u); if(len[u]>n)return 1; } } return 0; } int main() { n=rd(); m=rd(); K=rd(); memset(map,0x3f,sizeof map); // memset(val,-0x3f,sizeof val); for(int i=1;i<=n;i++) { // map[i][i]=0;// for(int j=1;j<=K;j++){b[i][j]=rd(); s[i][j]=rd();} } for(int i=1,x,y,z;i<=m;i++) { x=rd(); y=rd(); z=rd(); if(z<map[x][y])map[x][y]=z; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) // if(map[i][k]!=inf&&map[k][j]!=inf) map[i][j]=min(map[i][j],map[i][k]+map[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) // if(map[i][j]!=inf) { // val[i][j]=0;//至少是0 for(int k=1;k<=K;k++) if(b[i][k]!=-1&&s[j][k]!=-1) // if(b[i][k]>=0&&s[j][k]>=0) val[i][j]=max(val[i][j],s[j][k]-b[i][k]),r=max(r,val[i][j]); } l=0;r=inf; while(l<=r) { int mid=(l+r)/2; if(pd(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d",ans); return 0; }