公式图片来自洛谷题解
因为求V之和与P之和的比值的最大值。这个值不超过200
考虑到二分答案，设ans为最大值，则有
可以看出是01分数规划
那么每次就重新分配边的权值： ans*ci-vi
再判负环，有说明ans不成立，反之成立。
特别提一下：这里判负环是用dfs版的spfa，而不是bfs版的，dfs版的spfa在判负环上要更快。
#include<bits/stdc++.h> #define M 20003 #define N 7002 #define INF 2100000001 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } struct EDGE{ int nextt,to; double v,p,val; }w[M]; int n,m; int tot=0; int head[N],vis[N];double dis[N]; void add(int a,int b,int c,int d) { tot++; w[tot].v=c; w[tot].p=d; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } int SPFA(int now,double mid) { vis[now]=1; for(int i=head[now];i;i=w[i].nextt) { int v=w[i].to; double x=mid*w[i].p-w[i].v; if(dis[now]+x<dis[v]) { if(vis[v])return 0; else { dis[v]=dis[now]+x; vis[v]=1; if(!SPFA(v,mid))return 0; } } } vis[now]=0; return 1; } int check(double mid) { for(int i=1;i<=n;++i)vis[i]=0,dis[i]=INF; vis[n+1]=1; if(SPFA(n+1,mid))return 0; else return 1; } int main() { n=read(),m=read(); for(int i=1;i<=m;++i) { int a=read(),b=read(),v=read(),p=read(); add(a,b,v,p); } for(int i=1;i<=n;++i)add(n+1,i,0,0); double l=0,r=200; double ans=0; while(l+0.01<r) { double mid=(l+r)/2.0; if(check(mid))ans=mid,l=mid; else r=mid; } if(ans==0)printf("-1 "); else printf("%.1f ",ans); }