## 10331 - The Flyover Construction

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

Moderator: Board moderators

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

### 10331 - The Flyover Construction

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]

Qba
New poster
Posts: 4
Joined: Mon Jul 29, 2002 7:44 pm
Location: POLAND

### 10331

Hi !
Simple question

Is it possible - Two roads between two cities ?

example input:
2 2
1 2 1
2 1 1
|Q|

Qba
New poster
Posts: 4
Joined: Mon Jul 29, 2002 7:44 pm
Location: POLAND
Hi !

Maybe U must consider exaple input:

2 2
1 2 1
2 1 1

in my opinion example output is:
1 2
|Q|

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm
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]

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:

### 10331 Flyover Construction

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]

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
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...
Those Who Don't Know History are doomed to repeat it

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:
handle the capacity in the nodes!!??
Sorry..i cant understand what you mean very well...
Could you expain it more clearly...please?

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
He is referring to another problem "Power Transmission."
Not this one.

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
Oops

I make a mistake. I believe that you were talking about another problem. Sorry
Those Who Don't Know History are doomed to repeat it

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
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"

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

### input

Multiple edges between a pair of vertices is allowed.

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

### 10331

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

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

### input is correct. problem statement should be better.

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

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!

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

### Thanx....

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

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am
Thanks Andrey. Finally got AC after several months.

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