Page 1 of 2

10331 - The Flyover Construction

Posted: Wed Jul 17, 2002 2:19 am
by oker
Why did my code get WA? Help me, please!

[pascal]
program k331;

type
Tpoint=^Tr;
Tr=record
a :integer;
next :Tpoint;
end;

var
v,e,i :integer;
a,b,c :integer;
hash,link,dist,tt :array[1..100,1..100] of integer;
so :array[1..10000] of integer;
path :array[1..100,1..100] of Tpoint;
ma :pointer;

procedure solve(s,e :integer);

var
tp :Tpoint;

begin
if s=e then exit;
tp:=path[s,e];
while tp<>nil do begin
inc(tt[s,tp^.a]); inc(tt[tp^.a,s]);
solve(tp^.a,e);
tp:=tp^.next;
end;
end;



procedure work;

var
i,j,k,p,q,max,tso,tm :integer;
tem,tp :Tpoint;
begin
dist:=link;
fillchar(path,sizeof(path),0);
for i:=1 to v do
for j:=1 to v do path[i,j]:=nil;

for i:=1 to v do
for j:=1 to v do
if link[i,j]<>-1 then begin
new(tem); tem^.a:=j; tem^.next:=path[i,j];
path[i,j]:=tem; end;

for k:=1 to v do
for i:=1 to v do
if dist[i,k]<>-1 then
for j:=1 to v do
if (dist[k,j]<>-1) and ((dist[i,j]=-1) or (dist[i,j]>dist[i,k]+dist[k,j])) then begin
dist[i,j]:=dist[i,k]+dist[k,j];
tp:=path[i,j];
while tp<>nil do begin
tem:=tp^.next; dispose(tp); tp:=tem;
end;
new(tem); tem^.a:=k; tem^.next:=nil;
path[i,j]:=tem;
end else if (dist[k,j]<>-1) and (dist[i,j]=dist[i,k]+dist[k,j]) then begin
new(tem);
tem^.a:=k; tem^.next:=path[i,j];
path[i,j]:=tem;
end;
fillchar(tt,sizeof(tt),0);
for i:=1 to v-1 do
for j:=i+1 to v do
if dist[i,j]<>-1 then solve(i,j);

max:=0;

for i:=1 to v-1 do
for j:=i+1 to v do
if tt[i,j]>max then max:=tt[i,j];
tso:=0;
for i:=1 to v-1 do
for j:=i+1 to v do
if tt[i,j]=max then begin
inc(tso); so[tso]:=hash[i,j];
end;
for i:=1 to tso-1 do
for j:=i+1 to tso do
if so>so[j] then begin
tm:=so; so:=so[j]; so[j]:=tm;
end;
for i:=1 to tso-1 do write(so,' ');
writeln(so[tso]);
end;



begin
{ assign(input,'k331.in');
reset(input); }
while not eof(input) do begin
readln(v,e);
fillchar(link,sizeof(link),$FF);
fillchar(hash,sizeof(hash),$FF);
for i:=1 to e do begin
readln(a,b,c);
link[a,b]:=c; link[b,a]:=c;
hash[a,b]:=i; hash[b,a]:=i;
end;
mark(ma);
work;
release(ma);
end;
{ close(input); }
end.
[/pascal]

10331

Posted: Mon Jul 29, 2002 7:50 pm
by Qba
Hi !
Simple question ;-)

Is it possible - Two roads between two cities ?

example input:
2 2
1 2 1
2 1 1

Posted: Mon Jul 29, 2002 7:52 pm
by Qba
Hi !

Maybe U must consider exaple input:

2 2
1 2 1
2 1 1

in my opinion example output is:
1 2

Posted: Tue Jul 30, 2002 11:19 am
by oker
I've considered your opinion and changed my program. But still I got WA.
[pascal]

program k331;

type
Tpoint=^Tr;
Tr=record
a :integer;
next :Tpoint;
end;

var
v,e,i,j :integer;
a,b,c :integer;
link,dist,tt :array[1..100,1..100] of integer;
so :array[1..10000] of integer;
path,hash :array[1..100,1..100] of Tpoint;
ma :pointer;
tem :Tpoint;

procedure solve(s,e :integer);

var
tp :Tpoint;

begin
if s=e then exit;
tp:=path[s,e];
while tp<>nil do begin
inc(tt[s,tp^.a]); inc(tt[tp^.a,s]);
solve(tp^.a,e);
tp:=tp^.next;
end;
end;



procedure work;

var
i,j,k,p,q,max,tso,tm :integer;
tem,tp :Tpoint;
begin
dist:=link;
fillchar(path,sizeof(path),0);
for i:=1 to v do
for j:=1 to v do path[i,j]:=nil;

for i:=1 to v do
for j:=1 to v do
if link[i,j]<>-1 then begin
new(tem); tem^.a:=j; tem^.next:=path[i,j];
path[i,j]:=tem; end;

for k:=1 to v do
for i:=1 to v do
if dist[i,k]<>-1 then
for j:=1 to v do
if (dist[k,j]<>-1) and ((dist[i,j]=-1) or (dist[i,j]>dist[i,k]+dist[k,j])) then begin
dist[i,j]:=dist[i,k]+dist[k,j];
tp:=path[i,j];
while tp<>nil do begin
tem:=tp^.next; dispose(tp); tp:=tem;
end;
new(tem); tem^.a:=k; tem^.next:=nil;
path[i,j]:=tem;
end else if (dist[k,j]<>-1) and (dist[i,j]=dist[i,k]+dist[k,j]) then begin
new(tem);
tem^.a:=k; tem^.next:=path[i,j];
path[i,j]:=tem;
end;
fillchar(tt,sizeof(tt),0);
for i:=1 to v-1 do
for j:=i+1 to v do
if dist[i,j]<>-1 then solve(i,j);

max:=0;

for i:=1 to v-1 do
for j:=i+1 to v do
if tt[i,j]>max then max:=tt[i,j];
tso:=0;

for i:=1 to v-1 do
for j:=i+1 to v do
if tt[i,j]=max then begin
tp:=hash[i,j];
while tp<>nil do begin
inc(tso); so[tso]:=tp^.a; tp:=tp^.next;
end;
end;

for i:=1 to tso-1 do
for j:=i+1 to tso do
if so>so[j] then begin
tm:=so; so:=so[j]; so[j]:=tm;
end;
for i:=1 to tso-1 do write(so,' ');
writeln(so[tso]);
end;



begin
{ assign(input,'k331.in');
reset(input); }
while not eof(input) do begin
readln(v,e);
fillchar(link,sizeof(link),$FF);
mark(ma);
for i:=1 to v do
for j:=1 to v do hash[i,j]:=nil;
for i:=1 to e do begin
readln(a,b,c);
link[a,b]:=c; link[b,a]:=c;
new(tem); tem^.a:=i; tem^.next:=hash[a,b]; hash[a,b]:=tem;
new(tem); tem^.a:=i; tem^.next:=hash[b,a]; hash[b,a]:=tem;
end;
work;
release(ma);
end;
{ close(input); }
end.

[/pascal]

10331 Flyover Construction

Posted: Sun Sep 15, 2002 6:00 pm
by LTH
My method is use floyd and record the paths that is mininum cost
But i cant figure out why i get wrong answer...

i have write another program which is using "Brute Force"
and i generate a lot of test data and compare the answer
all of them are right.....thats strange...

I have used the common "Output Limit Exceeded" Method to make sure that
all of the ACM's test case will not have the following cases:

1. input a same road twice. (like 1 2 1\n 2 1 1)
2. same start and end
3. Cost <=0
4. V>1

is there any special cases or my algorithm is wrong?

[cpp]
/* @JUDGE_ID: 14949NT 10331 C++ "Floyd + DFS" */
#include <stdio.h>
#include <stdlib.h>

#define INT_MAX 2147483647

int exist[100][100],pathnum[100][100],paths[100][100][100],road_index[100][100],ans[10000];
long map[100][100],tmp;
bool changed[100][100];

int presort(const void *a,const void *b)
{
return *((int*)a)-*((int*)b);
}

void dfs(int a,int b)
{
int c;
if(exist[a]>=0||exist[a]>=0)
if(!changed[a])
exist[a]++;
for(c=0;c<pathnum[a];c++)
{
dfs(a,paths[a][c]);
dfs(paths[a][c],b);
}
}

void main()
{
int i,j,k,t,max,num,pnum,a,b,anum;
while(scanf("%d %d",&num,&pnum)!=EOF)
{
for(i=0;i<num;i++)
for(j=0;j<num;j++)
exist[j]=-1,map[j]=INT_MAX,pathnum[j]=0,changed[j]=0;
for(i=0;i<num;i++)
map=0;
for(i=0;i<pnum;i++)
{
scanf("%d %d %ld",&a,&b,&tmp);
map[a-1][b-1]=tmp;
map[b-1][a-1]=tmp;
exist[a-1][b-1]=0;
road_index[a-1][b-1]=i+1;
road_index[b-1][a-1]=i+1;
}
for(k=0;k<num;k++)
{
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(map[k]!=INT_MAX&&map[k][j]!=INT_MAX)
{
if(map[k]+map[k][j]<map[j])
{
changed[j]=1;
map[i][j]=map[i][k]+map[k][j];
pathnum[i][j]=0;
paths[i][j][pathnum[i][j]++]=k;
}
else if(map[i][k]+map[k][j]==map[i][j]&&i!=k&&k!=j)
paths[i][j][pathnum[i][j]++]=k;
}
}
}
}
for(i=0;i<num;i++)
for(j=i+1;j<num;j++)
dfs(i,j);
max=0,anum=0;
for(i=0;i<num;i++)
{
for(j=i+1;j<num;j++)
{
exist[i][j]=exist[i][j]+exist[j][i]+1;
if(exist[i][j]>max)
{
max=exist[i][j];
anum=0;
ans[anum++]=road_index[i][j];
}
else if(exist[i][j]==max)
ans[anum++]=road_index[i][j];
}
}
qsort(ans,anum,sizeof(int),presort);
for(i=0;i<anum;i++)
{
if(i>0)
printf(" ");
printf("%d",ans[i]);
}
printf("\n");
}
}

[/cpp]

Posted: Mon Sep 16, 2002 12:17 pm
by ithamar
I have not examined your code. But i know that a important part of this problem is to hanle the capacity in the nodes. How are you handling this? maybe this is the problem...

Posted: Mon Sep 16, 2002 5:51 pm
by LTH
handle the capacity in the nodes!!??
Sorry..i cant understand what you mean very well...
Could you expain it more clearly...please?

Posted: Tue Sep 17, 2002 3:58 am
by Shih-Chia Cheng
He is referring to another problem "Power Transmission."
Not this one.

Posted: Tue Sep 17, 2002 7:22 am
by ithamar
Oops :oops:

I make a mistake. I believe that you were talking about another problem. Sorry

Posted: Tue Sep 17, 2002 8:17 am
by Picard
try with this input

Code: Select all

7 8
1 2 2
1 3 2
2 4 3
3 4 3
4 5 3
4 6 3
5 7 2
6 7 2
it's symmetrical, output should be

Code: Select all

3 4 5 6
your output is only "3 4"

input

Posted: Mon Sep 30, 2002 5:09 am
by jingye
Multiple edges between a pair of vertices is allowed.

10331

Posted: Tue Nov 26, 2002 4:25 pm
by jaivasanth
Hi.....
Is there any problem with 10331 the flyover construction problem testdata.
My algo is....
First i do a Floyd warshall...
then i do a procedure to find all the shortest paths.. (not exactly DFS) but i do a procedure that is more optimal...i am pretty sure that works....
(bcoz first i did a dfs and it timed out) now my code runs for 4 seconds... and then gives a wrong answer..

Any good test data...??

please help
:-?

input is correct. problem statement should be better.

Posted: Mon Dec 02, 2002 9:41 am
by Andrey Mokhov
I used a lot of submissions to get AC on this problem. But I guess my first program was right according to the problem statement. The main problem was about counting usefulness of ribs. Lets consider the following graph.

............... ____(C)____
...............|....................|
(A)____(B).................(E)
...............|____(D)____|

(dots for alignment)

Upffs... well... not so bad :wink:

Let all the ribs be one unit long. Then there are two equal ways from A to E : A-B-C-E and A-B-D-E. My mistake was that in such a construction I thought that rib A-B is used twice and other ribs just once.
But only after some 10-20 submissions I realized that rib A-B is also used only once! That's strange as it is obvious that rib A-B is used more intensively than the others in the route from A to E. :-? Bad problem statement, I guess.

Perhaps you have the same bug, if not I may give you some outputs.

Good luck!

Thanx....

Posted: Mon Dec 02, 2002 8:00 pm
by jaivasanth
Thanx a lot ... That was the same mistake i had made too... i will correct it and try submitting :) Gosh... i was breaking my head as to why it failed ..

Posted: Wed Dec 04, 2002 8:22 am
by jingye
Thanks Andrey. Finally got AC after several months.

To future solvers:
There is at most ONE edge between two vertices.