Page 1 of 6

### 10397 - Connect the Campus

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

Posted: 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

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

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

Posted: 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

Posted: Wed Nov 20, 2002 2:10 pm
My output is just the same as yours.
But I still got TLE.

Posted: 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;
}

{

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

Posted: Tue Nov 26, 2002 7:43 am
Thanks, I have fixed my problem

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

Posted: Sun Dec 08, 2002 2:15 pm
Shantanu, hint: how many meanings does the variable k have in your program ?

### 10397:WHY WA?

Posted: 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
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;
}

### 10397 Connect the Campus, WA????

Posted: 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 Find(int element)
{
return element;
else
}

void UnionSet(int set1, int set2)
{
}

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]);
}

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]

Posted: Tue Jun 24, 2003 3:08 pm
-- Post removed by Observer (I find my old post unacceptably impolite ) --

Posted: 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

Posted: Wed Jun 25, 2003 11:47 am
-- Post removed by Observer --