## 10397 - Connect the Campus

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
You might want to look up "union find" for disjoint set..

http://www.cse.ust.hk/~dekai/271/notes/L09/L09.pdf

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
its a problem of mst.
u can use prims algo.
before that u have to set 0 to the given edge.
''I want to be most laziest person in the world''

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt
Thank u guys for ur help. I was giving up this problem but I got it ACed finally ---
Asmaa Magdi

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: ACC at last !

Sedefcho wrote:

Code: Select all

``Do you consider every possible connection between the nodes? That's O(n^2)!  ``
Yes, I consider all the connections, it's O(N^2), right. I just
use the standard Kruskal's algorithm, that's why I was so
sure I have to get ACC.
I've used O(n^2) for the connections too and got accepted. But I'm not happy with my running time.

How can I improve the part of building the graph (That is, to not consider all possible connections between nodes)? Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

marib
New poster
Posts: 2
Joined: Mon Apr 07, 2008 12:10 am

### Re:

asmaamagdi wrote:Thank u guys for ur help. I was giving up this problem but I got it ACed finally How?? What you have changed in the code?

marib
New poster
Posts: 2
Joined: Mon Apr 07, 2008 12:10 am

### Re:

sakhassan wrote:Thanks. But malloc doesn't bother me ..... I change my double variable to int and got AC ... I don't know why double makes trouble   Which double variable you change to int??

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

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

How?? What you have changed in the code?
used the union find algorithm.
---
Asmaa Magdi

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

### RTE

Help..!!
Why RTE ??

code:->

Code: Select all

``````#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
bool f;
vector<int> v,w;
vector< vector<int> > cn;

void fn(int k){
int i,j,n;
for(i=0;i<cn[k].size();i++){
n=cn[k][i];
if(f[n]){
f[n]=0;
j=0;
while(w[j]!=n)	j++;
w.erase(w.begin()+j);
v.push_back(n);
fn(n);
}
}
}

int main(){
int n,m,c,i,j,p,p1,p2;
int mn,d;
double ans;
while(cin>>n){
for(i=1;i<=n;i++){
cin>>c[i]>>c[i];
f[i]=1;
}
cin>>m;
cn.clear();
cn.resize(n+1);
while(m--){
cin>>i>>j;
cn[i].push_back(j);
cn[j].push_back(i);
}
v.clear();w.clear();
v.push_back(1);
for(i=2;i<=n;i++)
w.push_back(i);
f=0;
fn(1);
ans=0.0;
while(w.size()>0){
mn=(c[v]-c[w])*(c[v]-c[w])+(c[v]-c[w])*(c[v]-c[w]);
p1=v;p2=w;
p=0;
for(i=0;i<v.size();i++){
for(j=0;j<w.size();j++){
d=(c[v[i]]-c[w[j]])*(c[v[i]]-c[w[j]])+(c[v[i]]-c[w[j]])*(c[v[i]]-c[w[j]]);
if(d<mn){
mn=d;
p1=v[i];p2=w[j];
p=j;
}
}
}
ans+=sqrt(1.0*mn);
f[w[p]]=0;
fn(p2);
v.push_back(w[p]);
w.erase(w.begin()+p);
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
}
return 0;
}

``````

mrlinx
New poster
Posts: 3
Joined: Wed May 06, 2009 5:03 am

### 10397 - Connect the Campus

I get a Runtime Error from UVA and Segmentation Error in another system, probably with the same data tests...
My code checks for array bounds, but I can't seem to understand the failure.
Anyone can see the problem?

Code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_V 1000

typedef struct { int v1; int v2; float cost; } edge;
typedef struct point { int x; int y; } point;

edge edges[MAX_V];
point buildings[MAX_V];
int set[MAX_V];
int rank[MAX_V];

int compare (const void * a, const void * b) {
float cost_a = ((edge*) a)->cost, cost_b = ((edge*) b)->cost;
if(cost_a > cost_b) return 1;
else if(cost_a == cost_b) return  0;
else return -1;
}

void link(int a, int b) {
if(rank[a]>rank[b])
set[b]=a;
else {
set[a]=b;
if(rank[a]==rank[b])
rank[b]++;
}
}
int find(int a) {
if(set[a]!=a)
set[a]=find(set[a]);
return set[a];
}

int main (int argc, const char * argv[]) {
//freopen("input.txt", "rb", stdin);
//freopen("output.txt", "wb", stdout);

int num_buildings = -1, num_pipes = -1;
while (scanf("%d%*c", &num_buildings) == 1) {
int num_edges = 0;
for (int i=0; i<num_buildings; i++) {
scanf("%d %d%*c", &buildings[i].x, &buildings[i].y);
set[i]=i;
rank[i]=0;
}

for (int i=0; i<num_buildings; i++) {
for (int k=i+1; k<num_buildings; k++) {
edges[num_edges].v1 = i;
edges[num_edges].v2 = k;
edges[num_edges].cost = sqrt(pow((float) (buildings[i].x-buildings[k].x), 2) + pow((float) (buildings[i].y-buildings[k].y), 2));
num_edges++;
}
}

scanf("%d%*c", &num_pipes);
for (int i = 0, start, end; i<num_pipes; i++) {
scanf("%d %d%*c", &start, &end);
if (start >= 1 && end >= 1)
}

qsort(edges, num_edges, sizeof(edge), compare);

float minCost = 0;
for (int i=0; i<num_edges; i++) {
int v1 = find(edges[i].v1), v2 = find(edges[i].v2);
if (v1 != v2) {
minCost += edges[i].cost;
}
}
printf("%.2f\n", minCost);
}
return 0;
}

``````
Thanks for all the help. This is my last resort, I've spent quite a few hours looking at it, and testing several inputs.
Last edited by mrlinx on Sat May 09, 2009 1:26 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 10397 - Connect the Campus

Well, you seem to have allocated a very small array for edges:

Code: Select all

``````#define MAX_V 1000
...
edge edges[MAX_V];``````
There's almost 300000 edges in the worst case, not 1000.

mrlinx
New poster
Posts: 3
Joined: Wed May 06, 2009 5:03 am

### Re: 10397 - Connect the Campus

Hi,

Thanks for catching that. I solved my RE.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 10397 - Connect the Campus

Hi some one PLZ help me

i solve 10147 same as this problem
but i got WA in 10397   Code: Select all

``````CUT after ACC................. :lol:  :lol:
``````
Last edited by saiful_sust on Sun Sep 06, 2009 10:53 am, edited 1 time in total.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 10397 - Connect the Campus

Some PLZ help me................   saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 10397 - Connect the Campus

I solve this problem same code as i post here

the problem was double
i change the double type to int then it got acc.......  But what is wrong with double.?????????

regan
New poster
Posts: 4
Joined: Wed Apr 28, 2010 6:24 pm

### 10397 RTE & RTE !!!

Got RTE several times with my code....can any one help me by detecting the reason ....Here is my code...

Code: Select all

``````#include<iostream>
#include<math.h>
using namespace std;
long n,m,i,j,f,t,p;
double extra;
struct edge
{
long from;
long to;
double dist;
}edg;

struct node
{
long x;
long y;
}nod;
long parent(long u)
{
if(p[u]==-1) return u;
else
{
p[u]=parent(p[u]);
return p[u];
}
}

int fn(const void *a,const void *b)
{
edge *x=(edge *)a;
edge *y=(edge *)b;
if(x->dist-y->dist>0.00) return 1;
if(x->dist-y->dist>0.00) return -1;
return 0;
}

void FIND_MST()
{
qsort(edg,n*n,sizeof(edg),fn);

for(i=0;i<n*n;i++)
{
if(parent(edg[i].from)!=parent(edg[i].to))
{
extra
+=edg[i].dist;
p[parent(edg[i].from)]=parent(edg[i].to);
}
}
}

int main()
{
double aa,aaa;
while(scanf("%ld",&n)!=EOF)
{
for(i=0;i<n;i++)
{
p[i]=-1;
cin>>f>>t;
nod[i].x=f+10000;
nod[i].y=t+10000;
}
cin>>m;
for(i=0;i<m;i++)
{
cin>>f>>t;
edg[(f-1)*n+t-1].from=f-1;
edg[(f-1)*n+t-1].to=t-1;
p[parent(edg[(f-1)*n+t-1].from)]=parent(edg[(f-1)*n+t-1].to);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
edg[(i*n)+j].from=i;
edg[(i*n)+j].to=j;
if(i==j)
{
edg[(i*n)+j].dist=0.00;
}
else
{

edg[(i*n)+j].dist=sqrt((nod[i].x-nod[j].x)*(nod[i].x-nod[j].x)+(nod[i].y-nod[j].y)*(nod[i].y-nod[j].y));
}
}
}
extra=0.00;
FIND_MST();
printf("%.2lf\n",extra);
}
return 0;
}
``````