## 11090 - Going in Cycle!!

**Moderator:** Board moderators

### 11090 - Going in Cycle!!

Can this problem be done in O(n^3)?

My AC solution is O(n^4) in the worse case. More precisely, my solution is O(mn^2)

My AC solution is O(n^4) in the worse case. More precisely, my solution is O(mn^2)

I followed the link but couldn't get to any implementation (or pseudo code) for any of them, can you help with a link to the steps or implementation of any of these algorithms?Hadi wrote:There exist "many" O(mn) algorithms for this problem. See http://citeseer.ist.psu.edu/dasdan98experimental.html

2. There are some pseudo-codes at the end of that article

here is my program

Code: Select all

```
#include<iostream>
using namespace std;
int INF = 100000000;
const int MAX = 50;
int weight[MAX][MAX];
int n, m;
double min(double x, double y){
return x < y ? x : y;
}
double max(double x, double y){
return x > y ? x : y;
}
int d[MAX+1][MAX];
double MMC(){
//Initialize
int k, u, v, s = 0;
for(k = 0 ; k <= n ; k++)
for(u = 0 ; u < n ; u++)
d[k][u] = INF;
d[0][s] = 0;
//Compute the distances
for(k = 1 ; k <= n ; k++)
for(v = 0 ; v < n ; v++)
for(u = 0 ; u < n ; u++)
if(weight[u][v] < INF)
d[k][v] = min(d[k][v], d[k-1][u]+weight[u][v]);
//Compute lamda using karp's theorem
double lamda = INF;
for(u = 0 ; u < n ; u++){
double currentLamda = INF;
for(int k = 0 ; k < n ; k++)
if(d[n][u] < INF && d[k][u] < INF)
currentLamda = min(currentLamda, 1.0*(d[n][u]-d[k][u])/(n-k) );
lamda = min(lamda, currentLamda);
}
return lamda;
}
int main(){
freopen("1.in", "r", stdin);
int tt; cin >> tt;
for(int t = 0 ; t < tt ; t++){
cin >> n >> m;
int i;
for(i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
weight[i][j] = INF;
for(i = 0 ; i < m ; i++){
int l, r, c;
cin >> l >>r >> c;
weight[l-1][r-1] = min(c,weight[l-1][r-1]);
}
cout << "Case #" << t+1 << ": ";
double l = MMC();
if(l < INF){
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout << l;
}
else
cout << "No cycle found.";
cout << endl;
}
return 0;
}
```

1

3 4

1 2 2

2 3 4

3 1 6

1 3 6

any ideas?

To use it for a general graph, first step is detecting the strongly connected components which can be done using 2 dfs's in O(v+e). Then run the algorithm for each of the strongly connected components. If you don't know the algorithm for detecting Strongly Connected Components, tell.

I hope this can help ...

1- The Karp's pseudo code in the paper has a mistake in line 10, we should set lamda to a small value instead of INF.

2- I've applied Kosaraju's Algorithm for SCC as you've advised.

by the way do you know if these algorithms has extensions to cases more than finding a cycle, for example can we use them for solving the TopCoder problem you posted a link to?

also are these algorithms applied to find the maximum mean cycle?