Page 1 of 6

10397 - Connect the Campus

Posted: Fri Nov 08, 2002 10:45 am
by eloha
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
by Nak
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
by eloha
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
by eloha
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
by rakeb
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
by eloha
My output is just the same as yours.
But I still got TLE. :cry:

Posted: Thu Nov 21, 2002 1:29 pm
by rakeb
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

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

Posted: Tue Dec 03, 2002 6:02 pm
by Larry
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
by Caesum
Shantanu, hint: how many meanings does the variable k have in your program ?

10397:WHY WA?

Posted: Sun Apr 06, 2003 8:51 pm
by razibcse
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;
}

10397 Connect the Campus, WA????

Posted: Wed May 14, 2003 4:25 pm
by Chow Wai Chung
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]

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

Posted: Tue Jun 24, 2003 4:20 pm
by anupam
i didn't get the pictures of the problem. will any 1 please post it to board?
thanks..
--
anupam :oops: :oops:

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