题目大意：一张有向图，求一个环的点权和除以边权和，使得那个环在所有环中点权和除以边权和最大。
题目解析：最优比例环，令sigma(vi)/sigma(ei)<=ans,ans*sigma(ei)-sigma(vi)>=0,换句话说如果途中有负环，就不成立，上式成立需要所有换都不是负环，我们只需要二分ans即可；
AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> using namespace std; struct Edge { int to,w,next; }edge[5050]; int tol,head[1010],n,k,fun[1010]; void init() { memset(head,-1,sizeof(head)); tol=0; } void addedge(int u,int v,int w) { edge[tol].to=v; edge[tol].w=w; edge[tol].next=head[u]; head[u]=tol++; } bool spaf(double m) { queue<int>q; while(!q.empty())q.pop(); int inque[1010],in[1010]; double dis[1010]; memset(inque,0,sizeof(inque)); memset(in,0,sizeof(in)); for(int i=1;i<=n;i++) { dis[i]=0; inque[i]=1; in[i]=1; q.push(i); } while(!q.empty()) { int u = q.front(); q.pop(); inque[u]=0; for(int i = head[u];i!=-1;i=edge[i].next) { int v = edge[i].to; double t = m*edge[i].w-fun[v]; if(dis[v]>dis[u]+t) { dis[v]=dis[u]+t; if(!inque[v]) { inque[v]=1; q.push(v); in[v]++; if(in[v]>n) return true; } } } } return false; } int main() { while(scanf("%d%d",&n,&k)!=EOF) { init(); for(int i=1;i<=n;i++) scanf("%d",&fun[i]); for(int i=1;i<=k;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } double l=0,r=1000; while(r-l>1e-5) { double mid=(l+r)/2; if(spaf(mid)) l=mid; else r=mid; } printf("%.2f\n",l); } return 0; }
