Uva 11090 在环中

题目链接：http://vjudge.net/contest/143318#problem/A

题意： 求平均权值最小的回路。

分析：

平均权值不可能超过最大边，二分查，然后，由于是平均权值，就可以转换一下。

是否存在平均权值 < mid 的回路: w1 + w2 +.. +wk < k*mid

(w1-mid) + (w2-mid) +... + (wk-mid)<0;

只要精度够。 这个式子，就是一个负环，只要改变一下各条边的权值。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10000;

struct Edge
{
    int from,to;
    double dist;
};

struct BellmanFord
{
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool inq[maxn];
    double d[maxn];
    int p[maxn];
    int cnt[maxn];

    void init(int n)
    {
        this->n = n;
        for(int i = 0; i < n; i++) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, double dist)
    {
        edges.push_back((Edge)
        {
            from, to, dist
        });
        m = edges.size();
        G[from].push_back(m-1);
    }

    bool negativeCycle()
    {
        queue<int> Q;
        memset(inq, 0, sizeof(inq));
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; i++)
        {
            d[i] = 0;
            inq[0] = true;
            Q.push(i);
        }

        while(!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            inq[u] = false;
            for(int i = 0; i < G[u].size(); i++)
            {
                Edge& e = edges[G[u][i]];
                if(d[e.to] > d[u] + e.dist)
                {
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = G[u][i];
                    if(!inq[e.to])
                    {
                        Q.push(e.to);
                        inq[e.to] = true;
                        if(++cnt[e.to] > n) return true;
                    }
                }
            }
        }
        return false;
    }
};

BellmanFord solver;

bool test(double x)
{
    for(int i=0; i<solver.m; i++)
    {
        solver.edges[i].dist -= x;
    }

    bool ret = solver.negativeCycle();
    for(int i=0; i<solver.m; i++)
    {
        solver.edges[i].dist+=x;
    }
    return ret;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int kase = 1; kase<=t; kase++)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        solver.init(n);
        double ub = 0;
        for(int i=0; i<m; i++)
        {
            int u,v;
            double w;
            scanf("%d%d%lf",&u,&v,&w);
            u--;
            v--;
            ub = max(ub,w);
            solver.AddEdge(u,v,w);
        }
        printf("Case #%d: ",kase);
        if(!test(ub+1)) printf("No cycle found.
");

        else
        {
            double L = 0,R=ub;
            while(R-L>1e-3)
            {
                double M = L +(R-L)/2;

                if(test(M)) R = M;
                else L = M;

            }
            printf("%.2f
",L);
        }
    }


    return 0;
}