Problem G: Going in Cycle!!

Input: standard input

Output: standard output

 

You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has a weight, which equals to sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to find a cycle with the minimum mean.

 

Input

The first line of input gives the number of cases, N. N test cases follow. Each one starts with two numbers n and m. m lines follow, each has three positive number a, b, c which means there is an edge from vertex a to b with weight of c.

 

Output

For each test case output one line containing “Case #x: ” followed by a number that is the lowest mean cycle in graph with 2 digits after decimal place, if there is a cycle. Otherwise print “No cycle found.”.

 

Constraints

-           n ≤ 50

-           a, b ≤ n

-           c ≤ 10000000

 

Sample Input

Output for Sample Input

2
2 1
1 2 1
2 2
1 2 2
2 1 3

Case #1: No cycle found.
Case #2: 2.50

人生当中好好做的第二个bellman的题，原来bellman是这么玩的==之前知道bellman有判断负环的功能，比方说经典的“虫洞”问题，但也是基于求单源最短路的来说的。而这个题是”判断负环“。

题意：给定有向图，问所有环的最小平均值是多少，一看题意真心没思路，搜题解说是bellman二分减去中间值，使得出现负环~~恍然大悟ing 二分的时候犯了两个傻x错误l=mid;r=mid 小数的东西怎么能是+1呢？while循环是r-l>=0.0001怎么能是小于呢-==

#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const double inf=0x3f3f3f3f;
const int maxn=100;
int n,m,t;
double dist[maxn];
struct Edge
{
    int u,v;
    double cost;
    Edge(int _u=0,int _v=0,double _cost=0):u(_u),v(_v),cost(_cost){}
};
vector<Edge>E;
bool bellman(int start,int n)
{
    for(int i=1;i<=n;i++)dist[i]=inf;
    dist[start]=0;
    for(int i=1;i<n;i++)
    {
        bool flag=false;
        for(int j=0;j<E.size();j++)
        {
            int u=E[j].u;
            int v=E[j].v;
            double cost=E[j].cost;
            if(dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                flag=true;
            }
        }
        if(!flag)return true;
    }
    for(int j=0;j<E.size();j++)
        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)
            return false;
    return true;
}
bool judge(double x)
{
    for(int i=0;i<E.size();i++) E[i].cost-=x;
    bool flag=bellman(1,n);
    for(int i=0;i<E.size();i++) E[i].cost+=x;
    return flag;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("Case #%d: ",cas++);
        E.clear();
        double r=0.0;
        while(m--)
        {
            int a,b;
            double c;
            scanf("%d%d%lf",&a,&b,&c);
            E.push_back(Edge(a,b,c));
            if(c>r)r=c;
        }
      //  printf("r=%lf\n",r);
        if(judge(r+1))
        {
            printf("No cycle found.\n");
            continue;
        }
        double l=0.0,mid;
        while(r-l>=0.0001)
        {
            mid=(l+r)/2;
            for(int i=0;i<E.size();i++) E[i].cost-=mid;
            if(bellman(1,n)) l=mid;
            else r=mid;
            for(int i=0;i<E.size();i++) E[i].cost+=mid;
        }
        printf("%.2lf\n",r);
    }
    return 0;
}