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

Problemsetter: Mohammad Tavakoli Ghinani

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 = ; void add_edge(int id,int u) {
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];
add_edge(i,u);
} //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

    Original link :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem ...

  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

    CSS3 What's new ? 1. CSS3 Round the corners (border-radius), shadow (box-shadow), 2. Add special effects to words (text-shadow.), Linear gradient (gradient), rotate (tra ...

  9. Session variables lost after the call of Response.Redirect method

    From:  https://forums.asp.net/t/2096848.aspx?Session+variables+lost+after+the+call+of+Response+Redir ...

  10. Vue The key to bidirectional binding :Object.defineProperty()

    This method is amazing .vue.js and avalon.js It is through it to achieve two-way binding . and Object.observe It was also withdrawn by the sponsors of the draft . therefore defineProperty It's even more necessary to know . Let's start with a few lines of code ...