学步园

【题目大意】
给出一个有向图，问求一个回路，使得回路上的点权之和/边权之和 最大。
【解题思路】
转：此题是对01分数规划的应用,那么首先明白01分数规划的思想.
01整数规划问题就是求解方程(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)的最小值/最大值问题。其中xi = 0或1（i=1,2...n）对于此类问题我们可以通过二分来求解很接近答案的近似值。我们可以先令：
(a1*x1+a2*x2+..+an*xn)/(b1*x1+b2*x2+..+bn*xn)=L，则我们可以将此式转换为：x1*(a1-b1*L)+x2*(a2-b2*L)+...xn*(an-bn*L)=0，我们先定义一个估计值val，如果这个值使得上面的式子小于0我们就可以知道val>L,如果上式等于0，则val = L；如果大于0，则val<L,显然我们可以采用二分的思想求解次问题。

对于此题，设happy[u]为点u的欢乐值，w[u][v]为u-->v的边权值。要求的是happy[1]+happy[2]+...+happy[n] / w[1][2]+...+w[n-1][n] = ans,设ans就是所求的最大值。则移项，ans*w[u][v] - happy[v] = 0 .

建图：我们重新构造一幅图，使得边权为happy[v] - ans*w[u][v]。用SPFA算法，二分枚举ans，判断是否存在负权回路，若存在，说明ans偏小了，则增大ans，若不存在，则减小ans。

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const double eps=1e-3;
const int inf=100000000000;
struct nod
{
    int u,len,next;
} edge [5008];
int head[1014],cnt;
int n,m;
double weigth[1012];
void init()
{
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int len)
{
    edge[cnt].u=v;
    edge[cnt].len=len;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
//*****************************************//
bool spfa(double mid)
{
    double dist[1012];
    int visited[1012];
    int used[1016];
    int que[1002*1002];
    int i, v;
    double newdist;
    for (i = 1; i <= n; i++)
    {
        dist[i] = inf;
        visited[i] = false;
        used[i] = 0;
    }
    dist[1] = 0;
    int hea = 0, tail = 0;
    que[tail++] = 1;
    visited[1] = true;
    used[1]++;
    while (hea < tail)
    {
        int u = que[hea];
        visited[u] = false;
        hea++;
        for(i=head[u]; i!=-1; i=edge[i].next)
        {
            v = edge[i].u;
            newdist = mid * edge[i].len - weigth[v];  //新的边权值
            if (dist[u] + newdist < dist[v])
            {
                dist[v] = dist[u] + newdist;
                if (!visited[v])
                {
                    que[tail++] = v;
                    visited[v] = true;
                    used[v]++;
                    if (used[v] >= n)           //有负权环路
                        return false;
                }
            }
        }
    }
    return true;     //无负权环路
}
//*****************************************//
int main()
{
    while(cin >>n>>m)
    {
        init();
        for(int i=1; i<=n; i++)
            cin>>weigth[i];
        for(int i=0; i<m; i++)
        {
            int uu,vv,cc;
            cin>>uu>>vv>>cc;
            addedge(uu,vv,cc);
        }
        double mid;
        double L=0;
        double R=10066;
        double ans=0;
        while(R-L>=0.001)//二分
        {
            mid=(L+R)/2;
            if(spfa(mid))
                R=mid;
            else
            {
                ans=mid;
                L=mid;
            }
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}