给出一个有L个点P条边的**有向图（有向图记得了，判成无向图一直跑不出数据气死）**，每个点上的点权为F，每条边上的边权为T。请计算存在一个回路使得∑Fi/∑Ti最大。

同样进行二分建图，跑spfa判断是否存在环，由于是正环，所以取反就相当于判负环了。

只不过这题目数据有点水啊（不如说题目描述不够准确），网上很多人从1开始跑环的，但是也有人说是从哪个点都可以，仔细看了一下题目是从起始地点开始，也终于起始点，但是他并没有说起始点是1，而且又说是走过其他一系列的点，也就是说走过任何一个点？这样的话从哪个点开始跑都是没关系的，但是，题目又是给出了边数的啊？！喵喵喵？

还有，输出那里不是说没有环的话就输出0吗？为什么不特判也能过？喵喵喵？！

地址：http://poj.org/problem?id=3621

代码：

（这是bfs版的spfa，dfs版本的可以跑更快）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
#define MP pair<int, int>
typedef long long LL;
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-3;
const int maxn=5005;
int n, m;
double dis[maxn];
int inq[maxn], cnt[maxn], w[maxn];
vector<pair<int, int> > E[maxn];
queue<int> Q;
bool spfa(double mid){
    while(!Q.empty())Q.pop();
    for(int i=1;i<=n;i++){
        dis[i]=0;inq[i]=1;cnt[i]=1;
        Q.push(i);
    }
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        inq[u]=0;
        for(int i=0;i<E[u].size();i++){
            int v=E[u][i].first;
            double val=w[v]*1.0-1.0*mid*E[u][i].second;
            if(dis[v]<dis[u]+val){
                dis[v]=dis[u]+val;
                if(++cnt[v]>=n)return 1;
                if(inq[v])continue;
                Q.push(v);
                inq[v]=1;
            }
        }
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d", &n, &m)){
        for(int i=0;i<=n;i++)E[i].clear();
        for(int i=1;i<=n;i++)scanf("%d", &w[i]);
        int u, v, cost;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d", &u, &v, &cost);
            E[u].push_back(make_pair(v, cost));
        }
        double l=0, r=1000, mid;
        while(r-l>eps){
            mid=(l+r)/2;
            if(spfa(mid))l=mid;
            else r=mid;
        }
        if(l==0&&r==1000)printf("0\n");
        else printf("%.2f\n", l);
    }
    return 0;
}