10397 - Connect the Campus

[helloneo]

You might want to look up "union find" for disjoint set..
I found this from google..

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

[turcse143]

its a problem of mst.
u can use prims algo.
before that u have to set 0 to the given edge.

[asmaamagdi]

Thank u guys for ur help. I was giving up this problem but I got it ACed finally

[andmej]

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.

[marib]

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]

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]

How?? What you have changed in the code?

used the union find algorithm.

[Ron]

Help..!!
Why RTE ??

code:->

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
bool f[1000];
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[1000][2],i,j,p,p1,p2;
	int mn,d;
	double ans;
	while(cin>>n){
		for(i=1;i<=n;i++){
			cin>>c[i][0]>>c[i][1];
			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[1]=0;
		fn(1);
		ans=0.0;
		while(w.size()>0){
			mn=(c[v[0]][0]-c[w[0]][0])*(c[v[0]][0]-c[w[0]][0])+(c[v[0]][1]-c[w[0]][1])*(c[v[0]][1]-c[w[0]][1]);
			p1=v[0];p2=w[0];
			p=0;
			for(i=0;i<v.size();i++){
				for(j=0;j<w.size();j++){
					d=(c[v[i]][0]-c[w[j]][0])*(c[v[i]][0]-c[w[j]][0])+(c[v[i]][1]-c[w[j]][1])*(c[v[i]][1]-c[w[j]][1]);
					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]

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)
				link(find(start-1), find(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) {
				link(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.

[mf]

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]

Hi,

Thanks for catching that. I solved my RE.

[saiful_sust]

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: 

[saiful_sust]

Some PLZ help me................

[saiful_sust]

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]

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[10000];
double extra;
struct edge
{
 long from;
 long to;
 double dist;
}edg[1000000];

struct node
{
 long x;
 long y;
}nod[10000];
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[0]),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;
}