题意：
有向图中每个点有一个欢乐值，边有边权，要求一条环路，使环路上欢乐值得和/路径和最大。
分析：
二分参数，判断是否存在负权，这里判负圈没用spfa,用的是一种效率很高的方法。
代码：
//poj 3621
//sep9
#include <iostream>
#include <cmath>
using namespace std;
const int maxN=1024;
const int maxM=5012;
int n,m,e;
struct Edge
{int v,nxt;double c;
}edge[maxM];
int head[maxN],vis[maxN],cur;
double val[maxN],d[maxM],l,r,mid;bool dfs(int u)
{vis[u]=cur;for(int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].v;if(d[v]>d[u]+mid*edge[i].c-val[u]){d[v]=d[u]+mid*edge[i].c-val[u];if(vis[v]==cur) return true;else if(dfs(v)) return true;}}vis[u]=0; return false;
}bool neg_circle()
{for(int i=1;i<=n;++i)d[i]=0.0;memset(vis,0,sizeof(vis));for(cur=1;cur<=n;++cur)if(dfs(cur)) return true; return false;
}int main()
{while(scanf("%d%d",&n,&m)==2){e=0;memset(head,-1,sizeof(head));for(int i=1;i<=n;++i)scanf("%lf",&val[i]);for(int i=1;i<=m;++i){int a,b;double c;scanf("%d%d%lf",&a,&b,&c);edge[e].v=b;edge[e].c=c;edge[e].nxt=head[a];head[a]=e++; } l=0.0,r=1000.0;while(fabs(r-l)>1e-4){mid=(l+r)/2;if(neg_circle()) l=mid;elser=mid;}printf("%.2lf\n",mid);} return 0;
}