125 - Numbering Paths

[xbeanx]

Build your paths matrix (as you did) then use a modified Floyd Warshall to remove cycles.

ie

Code: Select all

for(int k = 0; k < nodes; k++)
	if(matrix[k][k] > 0)
		for(int i = 0; i < nodes; i++)
			for(int j = 0; j < nodes; j++)
				if(matrix[i][k] != 0 && matrix[k][j] != 0)
					matrix[i][j] = -1

Also, remove the constraints from your path building section (i!=k) it just messes things up. I would do this instead:

Code: Select all

for(int k = 0; k < nodes; k++)
	for(int i = 0; i < nodes; i++)
		for(int j = 0; j < nodes; j++)
			matrix[i][j] += matrix[i][k] * matrix[k][j]

[xbeanx]

It has to do with your pruning methods. You are not removing all the nodes along all the cycles. In fact, I could only find 1 test case where this failed, and even then it was only 1 element of the matrix that was off.

About the constraints (i!=k): You can safely ignore these constraints.

[Larry]

Mine was O(n^3). What I did was use Floyd-Warshall and then I used it again..

[junjieliang]

I'm not sure why your algorithm is O(n^6) but you can split them up and get into 2 parts that each runs in O(n^3) time.
O(n^3) time to run Floyd to find the number of paths,
O(n^3) time to find cycles.
Then for each (u, v), if the second part reports a cycle print -1, else print the number of paths found in part 1...

Hope this helps.

[xbeanx]

You are correct junjieliang. It was my mistake. My program is actually O(N^3). I should have thought a bit more before I started typing.

My program does exactly what you specified. Of course, my stupid mistake was saying that n^3 + n^3 == n^6

Thanks!

[Subeen]

I am having trouble with this problem. getting WA. please help me
here is my code:
[c]removed[/c]

[Dominik Michniewski]

Graphs in input can be multigraphs ....

Best regards
DM

[Subeen]

finally got AC. the bug is in my findpath function.

anyway, Dominik, what do u mean by

Graphs in input can be multigraphs ....

please, expain.

[Dominik Michniewski]

That means that input could be in form of:
I don't remember exact format, so I write idea only ...)
1->2
1->3
1->2
....
so from 1 to 2 exist two paths, not one ....

Best regards
DM

PS. This is my mistake, when I try to solve this problem

[Subeen]

thanks, Dominik.
but I think I didn't handle the case (same input more than once) but got AC.

[Dominik Michniewski]

Maybe test cases doesn't contian such cases or you have 'mistake' in your code such that you got correct answer I don't know ...
But I remember, that I found some IO in net from original contest and such cases were there. So I think, that probably exists in judge data. BTW.I got Acc when I handle multigraphs:-)

Best regards
DM

[Almost Human]

Is there any special or tricky input to consider ?

In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection

It means that if there is 5 intersection, then those intersections would be 0 , 1 , 2 , 3 , and 4 right ?

My idea to solve it is using a modified Floyd-Warshall algorithm.

I use edge[k+1][j] += edge[k][k] * edge[k][k][j] rather than
edge[k+1][j] = min ( edge[k][j] , edge[k][k] + edge[k][k][j] ). this is where I made the modification.

After that, I just print the result after checking if a cycle exist for all vertex v that included in the path of u-v.

Sorry about my bad english.

Any help and suggestion would be highly appreciated.

[Almost Human]

Is there any special or tricky input to consider ?

In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection

It means that if there is 5 intersection, then those intersections would be 0 , 1 , 2 , 3 , and 4 right ?

My idea to solve it is using a modified Floyd-Warshall algorithm.

I use edge[k+1][j] += edge[k][k] * edge[k][k][j] rather than
edge[k+1][j] = min ( edge[k][j] , edge[k][k] + edge[k][k][j] ). this is where I made the modification.

After that, I just print the result after checking if a cycle exist for all vertex v that included in the path of u-v.

Sorry about my bad english.

Any help and suggestion would be highly appreciated.

[Eduard]

I get WA when i submit it but it works correct for any test on my computer(also for multigraphs too)
Can someone help me.
This is my code.
[pascal]program acm125;
var a,b,c,s,sum:array[0..30,0..30] of integer;
number,i,j,n,k,u,v,max:integer;
procedure mult;
var i,j,k:integer;
begin
for i:=0 to n do
for j:=0 to n do
c[i,j]:=0;
for i:=0 to n do
for j:=0 to n do
for k:=0 to n do
begin
c[i,j]:=c[i,j]+b[i,k]*a[k,j];
end;
for i:=0 to n do
for j:=0 to n do
begin
s[i,j]:=s[i,j]+c[i,j];
b[i,j]:=c[i,j];
c[i,j]:=0;
end;
end;
begin
number:=-1;
while not eof do
begin
number:=number+1;
read(n);
for i:=0 to n do
for j:=0 to n do
a[i,j]:=0;
v:=0;
max:=0;
for i:=1 to n do
begin
read(u,v);
if max<u then max:=u;
if max<v then max:=v;
a[u,v]:=a[u,v]+1;
end;
n:=max;
for i:=0 to n do
for j:=0 to n do
begin
b[i,j]:=a[i,j];
s[i,j]:=a[i,j];
end;

for i:=1 to n do
mult;
for i:=0 to n do
for j:=0 to n do
sum[i,j]:=s[i,j];
for i:=1 to n+1 do
mult;
for i:=0 to n do
for j:=0 to n do
if sum[i,j]<>s[i,j] then sum[i,j]:=-1;
writeln('matrix for city ',number);
for i:=0 to n do
begin
for j:=0 to n do
write(sum[i,j],' ');
writeln;
end;
end;
end.[/pascal]

[Almost Human]

got AC, thanks