10034 - Freckles

[b3yours3lf]

thanks for reply, Grinder, but that's not the problem...
i have make stupid mistake at the part u point..

i compare set[k] with set[e[j].v2] but value of set[e[j].v2] will change in the loop..

[jandujar]

I recode this code

I have this code


[cpp]
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <math.h>

using namespace std;

/* Tipos */

struct EdgeOfGraph {
int vertex1,vertex2;
float weight;
};

typedef EdgeOfGraph edge;


typedef struct tipo{
float x;
float y;
}tipo;
typedef vector<tipo>punto;


/* Variables globales */

edge *edges,*edgesOfTree;
int v1,v2,nEdges,nVertices,*set;

punto puntos(101); //hay numero de puntos maximo de 100 el 0 no lo utilizo
int numeropuntos=0;



/* Make Set */
void Make_set(int set[])
{
int ctr1;
for(ctr1=1;ctr1<=set[0];ctr1++)
set[ctr1]=ctr1;
};

/* Link */
void Link(int set[],int x1,int x2)
{
int ctr1,ctr2,prevVal;
if(set[x1]==set[x2]) return ;
if(set[x1]<set[x2])
{prevVal=set[x2];
set[x2]=set[x1];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x2];
return ;
}
if(set[x2]<set[x1])
{prevVal=set[x1];
set[x1]=set[x2];
for(ctr1=1;ctr1<=set[0];ctr1++)
if(set[ctr1]==prevVal) set[ctr1]=set[x1];
return ;
}
}


float distancia(float x1,float y1, float x2, float y2){
return ((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}

void get_Edges(){

int ctrl=1;
int vertice1=1;
int vertice2=2;

while (ctrl<=nEdges){
while (vertice2<=numeropuntos){
edges[ctrl].vertex1=vertice1;
edges[ctrl].vertex2=vertice2;
edges[ctrl].weight=distancia(puntos[vertice1].x,puntos[vertice1].y,puntos[vertice2].x,puntos[vertice2].y);
vertice2++;
ctrl++;
}

vertice1++;
vertice2=vertice1+1;
}

}

/* Sort Edges */
void sort_Edges(edge edges[])
{
int ctr1,ctr2,ctr3;
edge temp;
for(ctr1=2;ctr1<=nEdges;ctr1++)
{
temp=edges[ctr1];
ctr2=ctr1;
while(ctr2>1 && temp.weight<edges[ctr2-1].weight)
{edges[ctr2]=edges[ctr2-1];
ctr2--;
};
if(ctr2!=ctr1)
edges[ctr2]=temp;
}
}

/* Kruskal */

void implementKruskal(edge edges[],edge edgesOfTree[],int set[])
{int ctr1,ctr2=1;
for(ctr1=1;ctr1<=edges[0].vertex1;ctr1++)
{if(set[edges[ctr1].vertex1]!=set[edges[ctr1].vertex2])
{
Link(set,edges[ctr1].vertex1,edges[ctr1].vertex2);
edgesOfTree[ctr2++]=edges[ctr1];
};
}
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=ctr2-1;
}

/* Recorremos los arcos sumando el resultado */
void muestraResultado(){
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges[i].weight);
}
printf("%.2lf\n",salida);
}



/* Ejecucion Kruskal */

int Kruskal(int nNodos)
{

set=(int *)malloc(sizeof(int) * (nNodos+1));
nEdges=nNodos*(nNodos -1)/2; //Maximo numero de nodos

edges=(edge *)malloc(sizeof(edge) * (nEdges+1));
edgesOfTree=(edge *)malloc(sizeof(edge) * (nEdges+1));

edges[0].vertex1=edges[0].vertex2=edges[0].weight=nEdges;
edgesOfTree[0].vertex1=edgesOfTree[0].vertex2=edgesOfTree[0].weight=nEdges;

// Carga las aristas
get_Edges();

// Ordena
sort_Edges(edges);

// Preparo el set
set[0]=nNodos;
Make_set(set);

// Ejecuto kruskal
implementKruskal(edges,edgesOfTree,set);

muestraResultado();


return 0;
}




/* A partir de aqui se acaba kruskal */


float distancia_minima(int indice){
float min=100000000;
float temp=100000000;
int i;

for(i=indice+1;i<numeropuntos;i++){

temp=distancia(puntos[indice].x,puntos[indice].y,puntos[i].x,puntos[i].y);
//cout<<"temp es:"<<temp<<endl;
if (temp<min){min=temp;}
}

return min;
}



int main(int argc, char *argv[])
{
int numerotest=0;
int i=0;
float x,y;
float salida=0;

// 200 es el tama

[shamim]

It seems that you have used the proper algorithm( Kruskal), but your code is far too long. I think you are considering extra things which is not required. For example, there is no need to define your own sort function, when a built in one is available.

Another thing, I have noticed in your code is you are passing parameters to the main function, which although not wrong, but is unnecessary.

You are also using dynamic memory allocation at various places, this is redundand. Since the number of points is given in advance, just use static array.

[jandujar]

Thank, I know the code isn't acurancy. (I will recode when it's necessary)

I have got a "kruskal" algorithm and then I have recode it.

Seems that works , but always give me Wrong Answer. Why?

[alu_mathics]

You can replace float by double.(infact all)
You wrote:

void muestraResultado(){
float salida=0;
int i;

for (i=1;i<=edgesOfTree[0].vertex1;i++){
salida+=sqrt(edges[i].weight);
}
printf("%.2lf\n",salida);
}

[jandujar]

I tried with all floats to doubles and don't work.
Thanks

Any other suggest?

[jandujar]

I Think the problem is output.

I write:

while(numtests>0)

cout<<number whith 2 decimal precition (redonded, shall i try truncated?)
cout<<endl;

end while


Is this correct?

[jandujar]

I have this input:
[cpp]
10

2
1.4 0.4
1.0 0.3

1
3.4 5.0

10
4.2 1.6
0.3 4.6
6.2 0.0
8.9 6.8
3.9 6.7
6.0 3.3
9.7 7.4
1.5 0.7
6.5 8.9
2.1 3.0

1
6.6 7.3

9
8.0 3.2
0.9 9.7
6.8 7.6
8.9 2.1
9.6 6.0
8.6 6.2
6.4 9.1
5.0 8.8
3.1 1.8

9
4.0 7.7
4.4 1.7
8.3 2.0
1.8 8.2
2.8 7.0
2.4 2.2
4.4 0.1
7.9 2.4
7.3 6.2

2
0.6 4.0
9.1 8.5

6
8.0 3.4
7.7 5.4
7.7 4.6
9.9 0.3
8.7 6.9
3.4 1.6

1
6.7 7.5

4
9.1 0.8
8.0 9.0
9.0 9.1
7.5 5.1

[/cpp]

And this output

[cpp]
0.41

0.00

22.69

0.00

16.15

15.90

9.62

8.37

0.00

9.21
[/cpp]

Is this correct? Thanks

Nota: I use this program to generate inputs.

[cpp]
#include <iostream.h>
#include <time.h>
#include <stdlib.h>

void puntorandom(){
int input1, input2;

input1 = rand() * 10 / (RAND_MAX + 1);
input2 = rand() * 10 / (RAND_MAX + 1);

cout<<input1<<"."<<input2;
}


int main()
{
int puntos,i,j;
srand(time(NULL));

cout<<10<<endl<<endl;

for (i=0; i<10 ; i++)
{
puntos= rand() * 10 / (RAND_MAX + 1) +1;
cout<<puntos<<endl;
for (j=0;j<puntos;j++){

puntorandom();
cout<<" ";
puntorandom();
cout<<endl;
}
cout<<endl;

}
}
[/cpp]

[Subeen]

jandujar, my acepted program prints the following output for your given input:

Code: Select all

0.41

0.00

23.94

0.00

20.06

18.22

9.62

12.42

0.00

9.52


[jandujar]

Thanks Subeen!!!

So, my code is incorrect (only works in some cases!!!!)

[jandujar]

Thanks to Subeen your output save me.

Finally I implement Prim's Algorithm but i hava "Presentation Errors"

Basicaly I do.



[cpp]
While (num--){
...
...

printf("%.2lf\n\n",salida);

}

[/cpp]

with

[cpp]
While (num--){
...
...

printf("%.2lf\n",salida);
if (num>0){
cout<<endl;
}

}

[/cpp]


I tried too , and have the same problem PE

[alu_mathics]

try this.

scanf("%d",&test);

while(test--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf(...);//inputs
}

//your algo

printf("%.2lf\n",salida);
if(test)printf("\n");
}

[adnan2nd]

I am getting presentation error WHY?????
Done by prims algo.

Code:
#include<stdio.h>
#include<math.h>
main()
{
int t[100][2],nr[101],n,m,i,j,k;
unsigned long c;
float cost[101][101];
float x[101],y[101],x1,y1;
float min,temp;
scanf("%lu",&c);
while(c)
{ min=0.0;c--;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%f %f",&x1,&y1);
x[i]=x1*10;y[i]=y1*10;
}
for(i=1;i<=n;i++) cost[i][i]=0.0;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
cost[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
cost[j][i]=cost[i][j];
}
for(i=2;i<=n;i++) nr[i]=1;
nr[1]=0;

for(i=1;i<n;i++)
{ m=-2;
for(j=2;j<=n;j++)
{
if(nr[j]!=0 && m==-2) m=j;
if(nr[j]!=0)
if(cost[j][nr[j]]<cost[m][nr[m]]) m=j;
}
temp=cost[m][nr[m]]*100;
temp=sqrt(temp);
min=min+temp ;
nr[m]=0;
for(k=2;k<=n;k++)
{
if(nr[k]!=0)
if(cost[k][nr[k]]>cost[k][m]) nr[k]=m;
}
}
printf("%.2f",min/100);
if(c!=0) printf("\n\n");
}
}

[Solaris]

I am not sure, but I got RTE for the following input

1

4
0.0 0.0
1.0 0.0
5.0 0.0
7.0 0.0

[troy]

Hi,

I keep getting WA for this problem.
I used Prims Alg to find the MST.

Is there a special Input case Im Missing?

Any suggestions?


// Code content Removed //.