11090 - Going in Cycle!!

[kp]

It also can be solved using binary search + Floyd.

I think you binary search for the mean value, but can you explain how you use floyd warshall to test if a cycle with this mean (or less) exists?

Well, I know about Karp's algo (see Cormen) but I solved it using Floyd only!
Here is my idea:
I want to know if cycle with mean less than R exists. Or in math terms:
sum(i from 1 to k)w(i)/k < R,
where w(i) weight of an edge

it is equivalent to sum(i from 1 to k)(w(i)-R) <0 !
so, all I need is to substract R from all weights and to test graph on negative cycle existance. Here comes the Floyd I just set all c=INF and launch it. If for some i c<0 then there is negative cycle.

[cpphamza]

Very interesting solution thanks alot. by the way I can't find Karp's algorithm in Cormen, is it really there? (actually I looked in the index and found nothing except for an excecise talking about minimum mean cycle).

[rio]

Please help me some I/O please?

Thanks in advance.

[mysword]

It also can be solved using binary search + Floyd.

only floyd is enough, no need to use binary search

[shakil]

Can any one give me some input and output............
thanks in advance ......

Code: Select all

#include<stdio.h>

long T,T1,i,j,k,n,m,x,y,z;
long sa[100][100],len[100][100];
long double max,t1,t2,r1,r2;

void main()
{


scanf("%ld",&T);

for(T1=1;T1<=T;T1++)
{

	scanf("%ld %ld",&n,&m);

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
		sa[i][j]=2000000000;
		len[i][j]=1;
		}


		for(i=0;i<m;i++)
		{
 		scanf("%ld %ld %ld",&x,&y,&z);
		x--;
		y--;
		if(sa[x][y]>z)
		sa[x][y] = z;
		}
     for(k=0;k<n;k++)
        for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			if(sa[i][k]!=2000000000&&sa[k][j]!=2000000000)
			{
			t1=sa[i][j];
			t2=sa[i][k]+sa[k][j];
			r1=len[i][j];
            r2=len[i][k]+len[k][j]; 
			t1=t1/r1;
			t2=t2/r2;
			if(t2<t1)
			{
			 sa[i][j]=sa[i][k]+sa[k][j];
			 len[i][j]=len[i][k]+len[k][j];
			}
			}


  max=2000000000;
   for(i=0;i<n;i++)
       if(sa[i][i]!=2000000000)
	   {
	        t1=sa[i][i];
			r1=len[i][i];
			t1=t1/r1;
			if(t1<max)
				max=t1;
		
	   }

	   printf("Case #%ld: ",T1);

if(max==2000000000)
printf("No cycle found.\n");
else
printf("%.2Lf\n",max);


}
}

[Hackson]

I have tried this problem with applying Kosaraju's algorithm and Karp's algorithm without success. My algorithm is as follows:
1. use Kosaraju's algorithm and store each SCC as separate graph
2. for each SCC, run Karp's algorithm and give the min mean cycle

I 've passed the test case provided from previous replies and I think it's not enough, is there any sample I/O?

Thanks a lot!!

[Hackson]

I got an AC code from my friend which uses binary search + warshall to solve. I generated some testdata and I found that there is an input which causes difference:

Code: Select all

1

18 63
17 9 10
3 16 12
18 4 5
13 3 4
18 5 11
12 16 4
13 2 1
15 4 13
6 10 7
10 6 17
17 3 9
2 5 6
3 4 17
4 8 8
8 12 2
3 12 4
4 10 12
7 4 2
17 4 3
2 16 8
2 3 1
6 18 6
6 3 8
13 7 5
14 15 4
15 7 15
2 8 16
16 10 11
17 7 18
1 9 18
4 7 16
7 9 15
4 12 19
11 2 6
2 13 17
5 8 15
2 9 8
11 6 11
7 2 12
4 18 10
18 1 20
6 5 2
15 1 18
15 18 13
9 14 12
16 14 5
2 4 13
6 17 12
5 16 8
11 4 6
10 3 12
8 3 1
3 8 12
17 12 12
18 9 6
1 12 10
6 16 12
9 10 20
1 11 8
8 13 11
15 14 11
16 1 15
12 13 18

The exact answer is 5.375 and my program gives 5.38 but the AC program gives 5.37 as output. Therefore I wonder if precision matters.

[Hackson]

OK seems nobody has idea on this problem, now I would like to post my code here and seek for any help, thanks

Code: Select all

#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

struct Edge{
        int u, v;
        double w;
        Edge(){u=v=0;w=0;}
        Edge(int a, int b, double c){ u=a;v=b;w=c; }
};

vector<Edge> E;
int death[100], vis[100], death_time, C[100][100], CT[100][100], G[1000][100], Gv[1000], g, n, m;
double W[100][100], d[101][100];
vector<Edge> GEdge[1000];
int Gn[1000][100];

void dfs(int v){
        vis[v] = 1;
        for (int i = 0 ; i < n ; ++i)
                if (!vis[i]&&CT[v][i])
                        dfs(i);
        death[death_time++] = v;
}

void rdfs(int v){
        G[g][Gv[g]++] = v;
        Gn[g][v] = 1;
        vis[v]=1;
        for (int i = n-1 ; i >= 0 ; --i)
                if (C[v][death[i]]&&!vis[death[i]])
                        rdfs(death[i]);
}

int min(int a, int b){ return a>b?b:a;}
double max(double a, double b){ return a<b-1e-8?b:a;}
double fmin(double a, double b){ return a-1e-8>b?b:a;}

int main(){
        int T, nc=0;
        scanf("%d", &T);
        while (T--){
                printf("Case #%d: ", ++nc);
                scanf("%d%d", &n, &m);
                memset(C, 0, sizeof(C));
                memset(CT, 0, sizeof(CT));
                memset(G, 0, sizeof(G));
                memset(Gv, 0, sizeof(Gv));
                memset(Gn, 0, sizeof(Gn));
                E.clear();
                for (int i = 0 ; i < m ; ++i){
                        int a, b;
                        double c;
                        scanf("%d%d%lf", &a, &b, &c);
                        E.push_back(Edge(--a, --b, c));
                        C[a][b] = 1;
                        CT[b][a] = 1;
                }
                memset(death, 0, sizeof(death));
                memset(vis, 0, sizeof(vis));
                death_time=0;
                for (int i = 0 ; i < n; ++i)  //Calculate Death Time
                        if (!vis[i])
                                dfs(i);
                memset(vis, 0, sizeof(vis));
                g = 0;
                for (int i = n-1 ; i >= 0 ; --i) //Construct all SCC
                        if (!vis[death[i]]){
                                rdfs(death[i]);
                                if (Gv[g]==1){ Gv[g] = 0; continue; }
                                GEdge[g].clear();
                                for (vector<Edge>::iterator t = E.begin(); t!=E.end();++t)
                                        if (Gn[g][t->u] && Gn[g][t->v]){
                                                GEdge[g].push_back(*t);
                                        }
                                g++;
                        }
                if (!g){ printf("No cycle found.\n"); continue;}
                double ANS = 1e9;
                for (int i = 0 ; i < g; ++i){
                        int s = G[i][0], V=Gv[i];
                        for (int k = 0 ; k <= n ; ++k)
                                for (int j = 0 ; j < n; ++j)
                                        d[k][j] = 1000000001;
                        d[0][s] = 0;
                        for (int k = 1 ; k <= V ; ++k)
                                for (vector<Edge>::iterator e = GEdge[i].begin(); e != GEdge[i].end(); ++e){
                                        if (d[k][e->v]-1e-8 > d[k-1][e->u]+e->w){
                                                d[k][e->v] = fmin(d[k][e->v], d[k-1][e->u] + e->w);
                                        }
                                }
                        for (int x = 0 ; x < V; ++x){
                                int nv = G[i][x];
                                double cANS = -1;
                                for (int y = 0 ; y < V; ++y)
                                                cANS = max(cANS, 1.*(d[V][nv] - d[y][nv])/(V-y));
                                ANS = fmin(cANS, ANS);
                        }
                }
                printf("%.2lf\n", ANS-1e-4);
        }
        return 0;
}

[DJWS]

This problem is known as 'the minimum mean cycle problem' or 'the minimum mean-weight cycle problem.' There are two different approaches to solve this problem:

The first approach is to project this problem to 'the minimum (cost-to-time) ratio problem.' The main idea to solve this problem is: set a proper ratio, transform the weight of edges in the graph, detect negative cycle and see if the ratio is correct. Usually we use binary search to find the ratio.

The second approach is a dynamic programming approach. The approach is described in CLRS practices. Its time complexity is O(V^3) with adjacency matrix / O(VE) with adjacency lists. By the way, if the graph have one more parts (or say, connected components), we can increase one vertex as source and add several zero-weighted edges from source to other vertices. Therefore all parts are connected.