10397 - Connect the Campus
Moderator: Board moderators
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?
Can anyone post more sample input and sample output?
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]
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]
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
[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
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
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
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;
}
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.
-
- 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.
#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]
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
[cpp]#include <string.h>Output
4.41
4.41
0.00
1.00
566.71
0.00
#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]
-- 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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-- 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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org