首页 > 代码库 > 图论trainning-part-1 D. Going in Cycle!!

图论trainning-part-1 D. Going in Cycle!!

2024-07-14 01:08:41   213人阅读

 

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 <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #include <queue>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<arc>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<int>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 }
View Code

 


联系
我们