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

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

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
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
My output is just the same as yours.
But I still got TLE.

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
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
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:
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:
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?

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

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 removed by Observer (I find my old post unacceptably impolite ) --
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:
i didn't get the pictures of the problem. will any 1 please post it to board?
thanks..
--
anupam
"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 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