Page 4 of 6
Posted: Thu Aug 30, 2007 5:03 am
You might want to look up "union find" for disjoint set..

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

Posted: Mon Mar 24, 2008 8:58 pm
its a problem of mst.
u can use prims algo.
before that u have to set 0 to the given edge.

Posted: Tue Mar 25, 2008 3:01 am
Thank u guys for ur help. I was giving up this problem but I got it ACed finally

### Re: ACC at last !

Posted: Wed Mar 26, 2008 4:44 am
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.

### Re:

Posted: Tue Apr 15, 2008 7:26 pm
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?

### Re:

Posted: Tue Apr 15, 2008 8:03 pm
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??

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

Posted: Tue Apr 15, 2008 8:09 pm
How?? What you have changed in the code?
used the union find algorithm.

### RTE

Posted: Thu Sep 11, 2008 1:45 pm
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;
}

``````

### 10397 - Connect the Campus

Posted: Wed May 06, 2009 5:08 am
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.

### Re: 10397 - Connect the Campus

Posted: Wed May 06, 2009 12:58 pm
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.

### Re: 10397 - Connect the Campus

Posted: Wed May 06, 2009 2:07 pm
Hi,

Thanks for catching that. I solved my RE.

### Re: 10397 - Connect the Campus

Posted: Fri Sep 04, 2009 6:49 pm
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:
``````

### Re: 10397 - Connect the Campus

Posted: Sat Sep 05, 2009 3:24 pm
Some PLZ help me................

### Re: 10397 - Connect the Campus

Posted: Sun Sep 06, 2009 11:00 am
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.?????????

### 10397 RTE & RTE !!!

Posted: Wed Jan 26, 2011 7:55 pm
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;
}
``````