Going in Cycle!! UVA - 11090（二分+判断环路 ）

题意：

　　给定一个n个点m条边的加权有向图，求平均权值最小的回路

解析：

　　首先肯定是想到找出环路  然后。。呵。。呵。。呵呵。。。

　　显然不现实！！

　　二分大法好 。。。。去猜结果 然后带入验证 。。。真是的。。很过分！

嗯！ 是的！

我参考一下UVA11478的代码 。。。建立超级源的做法。。竟然50ms  网上的用遍历每个没经过的点的做法2130ms  质的飞跃 。。。。。

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int head[maxn], vis[maxn], ans[maxn];

double d[maxn];

int cnt, n, m;

struct node

{

    int v, next;

    double w;

}Node[maxn];

void add(int u, int v, double w)

{

    Node[cnt].v = v;

    Node[cnt].w = w;

    Node[cnt].next = head[u];

    head[u] = cnt++;

}

int spfa()

{

    queue<int> Q;

    for(int i=; i<=n; i++)

    {

        Q.push(i);

        d[i] = ;

        vis[i] = ;

    }

    mem(ans, );

    while(!Q.empty())

    {

        int u = Q.front(); Q.pop();

        vis[u] = ;

        for(int i=head[u]; i!=-; i=Node[i].next)

        {

            node e = Node[i];

            if(d[e.v] > d[u] + e.w)

            {

                d[e.v] = d[u] + e.w;

                if(!vis[e.v])

                {

                    Q.push(e.v);

                    vis[e.v] = ;

                    if(++ans[e.v] >= n) return ;

                }

            }

        }

    }

    return ;

}

bool check(double x)

{

    bool flag = ;

    for(int i=; i<cnt; i++)

        Node[i].w -= x;

//    for(int i=1; i<=n; i++)

//        if(spfa(i))

//            flag = 1;

    if(spfa())

        flag = ;

    for(int i=; i<cnt; i++)

        Node[i].w += x;

    return flag;

}

void init()

{

    mem(head, -);

    cnt = ;

}

int main()

{

    int T, kase = ;

    scanf("%d", &T);

    while(T--)

    {

        init();

        int u, v;

        double w, x = , y = ;

        scanf("%d%d", &n, &m);

        for(int i=; i<m; i++)

        {

            scanf("%d%d%lf", &u, &v, &w);

            add(u, v, w);

            y = max(y, w);

        }

        printf("Case #%d: ",++kase);

        if(!check(y+)) printf("No cycle found.\n");

        else

        {

            while(y - x > 1e-)

            {

                double mid = x + (y-x)/(double);

                if(check(mid)) y = mid;

                else x = mid;

            }

            printf("%.2lf\n",x);

        }

    }

    return ;

}