0 6

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, NN test cases follow. Each one starts with two numbers n and mm 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

## Alternate Solution: Cho

Two points answer , Judge whether there is a negative weight loop .

``` #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX_N = ;
const double eps = 1e-;
const int edge = ;
int first[MAX_N],Next[edge],v[edge];
double w[edge];
bool inq[MAX_N];
int cnt[MAX_N];
double d[MAX_N];
int N,M;
double sum = ;
int e = first[u];
Next[id] = e;
first[u] = id;
}
bool bellman(double x) {
queue<int> q;
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt));
for(int i = ; i <= N; ++i) {
d[i] = ;
inq[i] = ;
q.push(i);
}
while(!q.empty()) {
int u = q.front(); q.pop();
inq[u] = ;
for(int e = first[u]; e != -; e = Next[e]) {
if(d[ v[e] ] > d[u] + w[e] - x) {
d[ v[e] ] = d[u] + w[e] - x;
if(!inq[ v[e] ]) {
q.push( v[e] );
inq[ v[e] ] = ;
if(++cnt[ v[e] ] > N) return true;
}
}
}
}
return false;
}
void solve() {
double l = ,r = sum;
while(r - l >= eps) {
//printf("l = %f r = %f\n",l,r);
double mid = (l + r) / ;
if(bellman(mid)) r = mid;
else l = mid;
}
if(bellman(sum + )) {
printf("%.2f\n",l);
} else {
printf("No cycle found.\n");
}
}
int main()
{
//freopen("sw.in","r",stdin);
int t;
scanf("%d",&t);
for(int ca = ; ca <= t; ++ca) {
scanf("%d%d",&N,&M);
for(int i = ; i <= N; ++i) first[i] = -;
sum = ;
for(int i = ; i < M; ++i) {
int u;
scanf("%d%d%lf",&u,&v[i],&w[i]);
sum += w[i];
}
//printf("sum = %f\n",sum);
printf("Case #%d: ",ca);
solve();
}
//cout << "Hello world!" << endl;
return ;
}```

## uva 11090 More articles about

1. UVA 11090 - Going in Cycle!!（Bellman-Ford）

UVA 11090 - Going in Cycle!! option=com_onlinejudge&Itemid=8&page=show_problem&category= ...

2. UVA - 11090 - Going in Cycle!!（ Two points + Differential restraint system ）

Problem  UVA - 11090 - Going in Cycle!! Time Limit: 3000 mSec Problem Description You are given a we ...

3. Training guide UVA - 11090（ shortest path BellmanFord+ Dichotomous negative ring ）

layout: post title: Training guide UVA - 11090( shortest path BellmanFord+ Dichotomous negative ring ) author: "luowentaoaa" catalog: ...

4. UVA 11090 Going in Cycle!! SPFA Judge negative loop + Two points

5. UVA 11090 - Going in Cycle!! SPFA

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&p ...

6. Uva 11090 In the ring

Topic link :http://vjudge.net/contest/143318#problem/A The question : Find the circuit with the minimum average weight . analysis : The average weight cannot exceed the maximum edge , Dichotomy , then , Because it's the average weight , Then you can switch ...

7. UVa 11090 Going in Cycle!!【Bellman_Ford】

The question : give n A little bit m Weighted Digraphs with edges , Find the circuit with the minimum average value I want to use DFS Looking for a ring ( It's too young), Find the average weight of each ring by comparison , But the code doesn't work , I don't think it's right Later, I read books = = What a clever way , Use ...

8. UVA 11090 Going in Cycle!!（ Two points answer + Negative link ）

In weighted digraph, find the circuit with minimum average weight . There's no idea at first , notice “ loop ”, The first idea is to find the connected component , It's a weighted graph again , There's no good idea , Then change the meaning : By finding the loop weight -> Negative link , For the minimum -> We often use the dichotomous answer . Two ...

9. UVA 11090 Going in Cycle!! Ring average weight （bellman-ford,spfa, Two points ）

The question : Given a n A little bit m Weighted Digraphs with edges , Find the average weight of the circuit with the minimum average weight ? Ideas : First , The existence of a ring in a graph is necessary to have a solution , Second, how much is the minimum average weight . Generally, this is the average weight of binary guess , Because it's hard to find the ring anywhere ...

## Random recommendation

1. c++ Some essays

1. A region of source code where any use of the unqualified name (that is, as a plain identifier) re ...

2. 【leetcode】Remove Nth Node From End of List（easy）

Given a linked list, remove the nth node from the end of list and return its head. For example, Give ...

3. adopt lua obtain nginx Built in variables for , Do some logical processing through these variables

Nginx There are many built-in variables , Such as : \$arg_PARAMETER This variable is contained in the query string GET request PARAMETER Value . \$args This variable is equal to the argument in the request line . \$binary_remote ...

4. django Forgienkey Field At the front desk js Do the processing

In my project, there is an option to choose a provincial city , The relationship between these two fields is one to many class Province(models.Model): # The provincial capital,       name = models.CharField(max ...

5. Find a good one to talk about PYTHON FILE IO Documents , Collection

Now I feel like I'm getting started , These two days , It can be used PYTHON Write something you want to achieve . But the document ,IO, code , mail , It's always a little incomplete . This document , it will work .. http://www.dabeaz.com/pyth ...

6. Customize Annotation

source :http://blog.csdn.net/lifetragedy/article/details/7394910 Concept Take a look at the simplest annotation Example @Target(Element ...

7. Symbol() How to use

brief introduction :ES5 Object property names are strings , This can easily cause property name conflicts , For example, a project is huge , It's not developed by one person Of , It may cause variable name conflict , I wish I had a unique name , In this way, property name conflicts can be prevented fundamentally . This is ...

8. css Learning notes of