10397 - Connect the Campus

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

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

10397 - Connect the Campus

Post by eloha » Fri Nov 08, 2002 10:45 am

The algorithm I use for this problem is something like minimal spanning tree. And I got WA.
Can anyone post more sample input and sample output?

Nak
New poster
Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

Post by Nak » Fri Nov 08, 2002 1:11 pm

Did you consider a disconnected input graph?

Input:

4
0 0
0 1
1 0
1 1
2
1 2
3 4

Output should be 1.00

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Sat Nov 09, 2002 5:22 pm

Nak wrote:Did you consider a disconnected input graph?
Yes, I do not consider this. Thanks for your help. I will modify my program and try again.

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Fri Nov 15, 2002 5:14 am

I have modified my program and now I got TLE.
Can anyone help me? The following is my source code.
[c]#define UNUSED -1
#define MaxBuilding 751
typedef struct { double x,y;} Building;
Building b[MaxBuilding];
int N,concom;
int ct[MaxBuilding][MaxBuilding],visited[MaxBuilding];

void dfs(int v,int mark)
{ int j;
visited[v]=mark;
for(j=0;j<N;j++)
if(visited[j]==UNUSED && ct[v][j])
dfs(j,mark);
}

int find_connected_component()
{ int i,concom;
for(i=concom=0;i<N;i++) if(visited==i) concom++;
return concom;
}

main()
{
int i,j,M,building1,building2,basegroup,bi;
double total_cable_length,this_min,last_min, d[MaxBuilding][MaxBuilding];
while(scanf("%d",&N)==1)
{
for(i=0;i<N;i++) for(j=0;j<N;j++) ct[j]=0;
for(i=0;i<N;i++) { scanf("%lf %lf",&b.x,&b.y); }
for(i=0;i<N-1;i++) for(j=i+1;j<N;j++) d[j]=d[j]=(b.x-b[j].x)*(b.x-b[j].x) + (b.y-b[j].y)*(b.y-b[j].y);
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d %d",&building1,&building2);
building1--; building2--;
ct[building1][building2]=ct[building2][building1]=1;
}

total_cable_length=0.0;

/* find how many connected components */
for(i=0;i<N;i++) visited[i]=UNUSED;
for(i=0;i<N;i++)
if(visited[i]==UNUSED)
dfs(i,i);

/* use greedy algorithm and minimum spanning tree */
basegroup=visited[0];
while(find_connected_component()>1)
{
last_min=9999999999.0;
for(i=0;i<N;i++)
{
if(visited[i]==basegroup) continue;
this_min=9999999999.0;
for(j=0;j<N;j++)
{
if(visited[j]==basegroup)
if(d[i][j]<this_min) this_min=d[i][j];
}
if(this_min<last_min) { last_min=this_min; bi=i; }
}

for(i=0;i<N;i++) if(visited[i]==bi) visited[i]=basegroup;
total_cable_length += sqrt(last_min);
}
printf("%.2lf\n",total_cable_length);
}
return 0;
}
[/c]

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Fri Nov 15, 2002 3:29 pm

i am not too sure about ur MST algorithm, i think it's better you use kruskal or prim. i assigned cost 0.0 for the existing cables and used kruskal.

[cpp]
scanf("%ld",&nc);
while(nc--)
{
scanf("%ld%ld",&i,&j);
m[j]=0.0;
}
[/cpp]

INPUT:
6
0 0
200 50
100 200
50 300
300 200
300 300
2
3 4
5 6

6
0 0
200 50
100 200
50 300
300 200
300 300
5
1 2
2 3
3 4
4 5
5 6

OUTPUT:
566.71
0.00

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan

Post by eloha » Wed Nov 20, 2002 2:10 pm

My output is just the same as yours.
But I still got TLE. :cry:

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Thu Nov 21, 2002 1:29 pm

as i told before i think there is something wrong with ur MST algorithm
try this one

[cpp]

struct ed
{
long src,dst;
double cost;
}h[10000000],zero;

double m[1000][1000];
long parent[1000],tree[1000][2];

void insert(ed x,long n)
{
long i=n;
while(i>1 && h[i/2].cost>x.cost)
{
h=h[i/2];
i/=2;
}
h=x;
}

void adjust(long n)
{

long j=2;
ed item=h[1];
while(j<=n)
{
if(j<n && h[j].cost>h[j+1].cost)
j++;
if(item.cost<=h[j].cost)
break;
h[j/2]=h[j];
j*=2;
}
h[j/2]=item;

}

ed delmin(long n)
{
ed x;
if(n>=1)
{
x=h[1];
h[1]=h[n];
adjust(n-1);
return x;
}

return zero;


}

long find(long i)
{
while(parent!=-1)
i=parent;
return i;
}

void Union(long i,long j)
{
long t1,t2;
t1 =parent[j];
parent[j]=i;
while(t1!=-1)
{
i=parent[t1];
parent[t1]=j;
j=t1;
t1=i;

}
}


double kruskal(long n,long e)
{
long i,r1,r2;
double mincost=0.0;
ed t;
for(i=1;i<=n;i++)
parent=-1;
i=0;
while(i<n-1 && e>0)
{
t=delmin(e--);
r1=find(t.src);
r2=find(t.dst);
if(r1!=r2)
{
i++;
tree[0]=t.src;
tree[1]=t.dst;
mincost+=t.cost;
Union(t.src,t.dst);
}

}

if(i!=n-1)
return -1;
return mincost;

}
[/cpp]

this is my kruskal MST algorithm
just call it to get the min cost and creat a MST
rakEb

Shantanu
New poster
Posts: 8
Joined: Sun Oct 20, 2002 6:44 am

Post by Shantanu » Tue Nov 26, 2002 7:43 am

Thanks, I have fixed my problem
Last edited by Shantanu on Sun Dec 15, 2002 8:13 am, edited 1 time in total.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Dec 03, 2002 6:02 pm

rakeb, I used the same idea with changing the weights to 0.0. I think this was a great idea!

I used Prim's algorithm and it worked anyhow..

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sun Dec 08, 2002 2:15 pm

Shantanu, hint: how many meanings does the variable k have in your program ?

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

10397:WHY WA?

Post by razibcse » Sun Apr 06, 2003 8:51 pm

I used the prim algorithm for this problem.
First, the numbers of connected buildings are taken...
these values are inserted in the 'edge' list and near_node of
the corresponding values are made -1.
then prim() function determines the new nodes connected with
the nodes already in the 'edge' and updates the mincost value.
Is my approach is wrong or is there more better way of solving the problem?


#include <stdio.h>
#include <math.h>
#define MAX_N 1000
#define INF 200000

long n,m;
double grid[MAX_N][MAX_N];
long near_node[MAX_N],edge[MAX_N][2];

double prim();
double SQUARE(double a,double b);
void main()
{

long i,j,q_x,q_y;
double result,x_dif,y_dif,dif,x[MAX_N],y[MAX_N];
while(scanf("%ld",&n)==1)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
grid[j]=INF;

for(i=0;i<n;i++)
{
scanf("%lf %lf",&x,&y);
for(j=0;j<=i;j++)
{
x_dif=x[j]-x;
y_dif=y[j]-y;
if(x_dif<0)
x_dif*=(-1);
if(y_dif<0)
y_dif*=(-1);
dif=SQUARE(x_dif,y_dif);
grid[j]=dif;
grid[j]=dif;
}
}


for(i=0;i<n;i++)
near_node=0;

scanf("%ld",&m);
for(i=0;i<m;i++)
{
scanf("%ld %ld",&q_x,&q_y);
edge[0]=q_x-1;
edge[1]=q_y-1;
near_node[q_x-1]=near_node[q_y-1]=-1;
}
result=prim();
printf("%.2lf\n",result);

}
}

double SQUARE(double a,double b)
{
double aa,bb,cc,dd;
aa=a*a;
bb=b*b;
cc=aa+bb;
dd=sqrt(cc);
return dd;
}

double prim()
{
long j,k,x,y,z;
double min,mincost=0;
for(z=0;z<(n-m-1);z++) // as the number of edges in the 'edge' is m,
{ // the new edges are inserted from the (m+1)th position.
min=INF;
for(j=0;j<n;j++)
for(k=0;k<n;k++)
if(near_node[j]==-1 && near_node[k]!=-1 && grid[j][k]<min)
{
min=grid[j][k];
x=j;
y=k;
}

mincost+=min;
edge[m+z][0]=x;
edge[m+z][1]=y;
near_node[y]=-1;
}


return mincost;
}
Wisdom is know what to do next; virtue is doing it.

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

10397 Connect the Campus, WA????

Post by Chow Wai Chung » Wed May 14, 2003 4:25 pm

I had try many test data, it seems nothing wrong, can anyone tell me what wrong with my program?? Thank you.

Input
4
103 104
104 100
104 103
100 100
1
4 2
4
103 104
104 100
104 103
100 100
1
4 2
1
100 500
0
4
0 0
0 1
1 0
1 1
2
1 2
3 4
6
0 0
200 50
100 200
50 300
300 200
300 300
2
3 4
5 6
6
0 0
200 50
100 200
50 300
300 200
300 300
5
1 2
2 3
3 4
4 5
5 6
Output
4.41
4.41
0.00
1.00
566.71
0.00
[cpp]#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct edges
{
int v1;
int v2;
double length;
}Edge;

int comp(const void *a,const void *b)
{
if (((Edge *)a)->length > ((Edge *)b)->length) return 1;
if (((Edge *)a)->length < ((Edge *)b)->length) return -1;
return 0;
}

int link[750];

int Find(int element)
{
if(link[element]==element)
return element;
else
return Find(link[element]);
}

void UnionSet(int set1, int set2)
{
link[set2]=set1;
}

void Union(int element1, int element2)
{
UnionSet(Find(element1),Find(element2));
}

void Kruskal(Edge *e,int nb,int ne,int nc)
{
int y;
double sum=0;

qsort(e,ne,sizeof(Edge),comp);

y=0;
while(nb>nc+1)
{
if(Find(e[y].v1)!=Find(e[y].v2))
{
sum+=e[y].length;
Union(e[y].v1,e[y].v2);
nb--;
}
y++;
}
printf("%.2lf\n",sum);
}

int main()
{
Edge e[300000];
int pos[750][2],NumB,NumC,NumE,y,z,t1,t2;
while(scanf("%d\n",&NumB)==1)
{
for(y=0;y<NumB;y++)
{
scanf("%d %d",&pos[y][0],&pos[y][1]);
link[y]=y;
}

scanf("%d",&NumC);
for(y=0;y<NumC;y++)
{
scanf("%d %d",&t1,&t2);
Union(t1-1,t2-1);
}

/* compute the distance */
NumE=0;
for(y=0;y<NumB;y++)
for(z=y+1;z<NumB;z++)
{
e[NumE].v1=y;
e[NumE].v2=z;
e[NumE++].length=sqrt((pos[y][0]-pos[z][0])*(pos[y][0]-pos[z][0])+(pos[y][1]-pos[z][1])*(pos[y][1]-pos[z][1]));
}

Kruskal(e,NumB,NumE,NumC);
}
return 0;
}[/cpp][/code]

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jun 24, 2003 3:08 pm

-- Post removed by Observer (I find my old post unacceptably impolite :wink: ) --
Last edited by Observer on Fri Jan 13, 2006 6:23 pm, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Jun 24, 2003 4:20 pm

i didn't get the pictures of the problem. will any 1 please post it to board?
thanks..
--
anupam :oops: :oops:
"Everything should be made simple, but not always simpler"

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Jun 25, 2003 11:47 am

-- Post removed by Observer --
Last edited by Observer on Fri Jan 13, 2006 6:22 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 103 (10300-10399)”