11090 - Going in Cycle!!

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post by kp »

cpphamza wrote:
kp wrote: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
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm

Post by 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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio »

Please help me some I/O please?

Thanks in advance.

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by mysword »

kp wrote:It also can be solved using binary search + Floyd.
only floyd is enough, no need to use binary search

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

WA ??????

Post by 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);


}
}
SHAKIL

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by 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!! :oops:
Solving problem is a no easy task...

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by 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.
Solving problem is a no easy task...

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by 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;
}
Solving problem is a no easy task...

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Re: 11090 - Going in Cycle!!

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

Post Reply

Return to “Volume 110 (11000-11099)”