分数规划+二分   最优比率环   

不是很难 本题中没有说明从哪个点开始 不过好像默认为1就可以过  poj数据又水了 

里面的用spfa判定部分还是不太懂 

代码及其注释：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const double eps=1e-5;const int N=1001;const int M=5005;int head[N];//邻接表头struct node{ int j,k; int next;}side[M];边int value[N];//点的价值bool in[N];//是否在队列中int innum[N];//如队列次数double dist[N];//记录queue
           
            str;void build(int x,int t)//建树{ side[t].next=head[x]; head[x]=t;}bool spfa(double L,int n)//看是否有正环 如果有返回true{ while(!str.empty()) str.pop(); for(int i=1;i<=n;++i) { dist[i]=0.0; str.push(i); } memset(in,true,sizeof(in)); memset(innum,0,sizeof(innum)); while(!str.empty()) { int x=str.front(); str.pop(); in[x]=false; int t=head[x]; while(t!=-1) {//cout<
            
             <
             
              =n)//有环 return true; } } t=side[t].next; } } return false;}int main(){ // freopen("data.txt","r",stdin); int n,m; while(scanf("%d %d",&n,&m)!=EOF) { memset(head,-1,sizeof(head)); for(int i=1;i<=n;++i) scanf("%d",&value[i]); for(int i=1;i<=m;++i) { int x; scanf("%d %d %d",&x,&side[i].j,&side[i].k); build(x,i); } double l=1.0,r=200.0; while(r-l>eps)//用二分 不断向答案逼近 { double mid=(l+r)/2.0; if(spfa(mid,n)) l=mid; else r=mid; } printf("%.2f\n",l); } return 0;}