D. Going in Cycle!!

Time Limit: 3000ms

Memory Limit: 131072KB

64-bit integer IO format: 

%lld      Java class name: Main

 

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..

 

- n ≤ 50

- a, b ≤ n

- c ≤ 10000000

 

Sample Input

 

2

2 1

1 2 1

2 2

1 2 2

2 1 3

 

Output for Sample Input

Case #1: No cycle found.

Case #2: 2.50

 

解题：二分+spfa负权回路判定

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                10 #define LL long long11 #define INF 0x3f3f3ff12 using namespace std;13 const int maxn = 60;14 const double exps = 1e-3;15 struct arc {16 int to;17 double w;18 };19 20 vector
                
                 g[maxn];21 int cnt[maxn],n,m;22 double d[maxn];23 bool vis[maxn];24 bool spfa() {25 int i,j,v,u;26 queue
                 
                  q;27 for(i = 1; i <= n; i++) {28 q.push(i);29 d[i] = INF;30 vis[i] = true;31 cnt[i] = 1;32 }33 d[1] = 0;34 while(!q.empty()) {35 u = q.front();36 q.pop();37 vis[u] = false;38 for(i = 0; i < g[u].size(); i++) {39 v = g[u][i].to;40 if(d[v] > d[u]+g[u][i].w) {41 d[v] = d[u]+g[u][i].w;42 if(!vis[v]) {43 vis[v] = true;44 cnt[v]++;45 q.push(v);46 if(cnt[u] > n) return true;47 48 }49 }50 }51 }52 return false;53 }54 void modify(double val) {55 for(int i = 1; i <= n; i++) {56 for(int j = 0; j < g[i].size(); j++) {57 g[i][j].w += val;58 }59 }60 }61 bool test(double val) {62 modify(-val);63 bool it = spfa();64 modify(val);65 return it;66 }67 int main() {68 int t,i,j,u,v,k = 1;69 double lt,rt,mid,w;70 scanf("%d",&t);71 while(t--) {72 scanf("%d%d",&n,&m);73 for(i = 0; i <= n; i++)74 g[i].clear();75 lt = INF;76 rt = 0;77 for(i = 0; i < m; i++) {78 scanf("%d%d%lf",&u,&v,&w);79 g[u].push_back((arc) {v,w});80 if(lt > w) lt = w;81 if(w > rt) rt = w;82 }83 printf("Case #%d: ",k++);84 if(test(rt+1.0)) {85 while(rt-lt > exps) {86 mid = lt+(rt-lt)/2;87 if(test(mid)) rt = mid;88 else lt = mid;89 }90 printf("%.2f\n",rt);91 } else printf("No cycle found.\n");92 }93 return 0;94 }