Pagini recente » Cod sursa (job #1913462) | Cod sursa (job #47407) | Cod sursa (job #1897862) | Cod sursa (job #2639662) | Cod sursa (job #647262)
Cod sursa(job #647262)
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cmath>
#define infile "retea2.in"
#define outfile "retea2.out"
#define n_max 4005
#define INF 1<<30
#define pb push_back
#define mkp make_pair
#define FOR(g,it) \
for(vector<int> ::iterator it = g.begin(); it!=g.end(); ++it)
using namespace std;
struct punct
{ int x,y; } p[n_max];
struct muchie
{
int A, B;
double c;
} apm[2*n_max];
bitset < n_max > uz;
int dim_p, dim_apm ;
int T[n_max], R[n_max];
int X, Y;
int N, M;
double cost_apm;
inline double dist(punct A, punct B)
{ return sqrt( (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) ); }
int mycmp (const muchie &A, const muchie &B)
{ return A.c < B.c; }
int cauta (int x)
{
int r,y;
for(r=x; T[r]!=r; r=T[r]);
while(T[x]!=x)
{
y = T[x];
T[x] = r;
x = y;
}
return r;
}
void uneste(int x, int y)
{
if(R[x] < R[y])
T[x] = T[y];
else
T[y] = x;
if(R[x] == R[y])
R[x]++;
}
void kruskal()
{
sort(apm+1, apm+dim_apm+1, mycmp);
int nrm = 0, n = dim_apm;
dim_apm = 0;
for(int i=1;i<=n && nrm < dim_p - N; i++)
{
int m1 = cauta(apm[i].A);
int m2 = cauta(apm[i].B);
if(m1!=m2)
{
uneste(m1,m2);
apm[++dim_apm] = apm[i];
cost_apm += apm[i].c;
nrm++;
}
}
}
void citeste()
{
freopen(infile,"r",stdin);
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++)
{
scanf("%d %d", &X, &Y);
p[++dim_p].x = X;
p[dim_p].y = Y;
}
T[1] = 1;
R[1] = 1;
for(int i=2;i<=N;i++)//UNESC CENTRALELE
{
T[i] = i;
R[i] = i;
uneste(i,1);
}
for(int i=N+1; i<=N+M;i++)
{
scanf("%d %d",&X, &Y);
p[++dim_p].x = X;
p[dim_p].y = Y;
for(int j=1;j<dim_p;j++)
{
apm[++dim_apm].c = dist(p[dim_p],p[j]);
apm[dim_apm].A = j;
apm[dim_apm].B = dim_p;
}
T[dim_p] = dim_p;
R[dim_p] = 1;
}
fclose(stdin);
}
void afiseaza()
{
freopen(outfile,"w",stdout);
printf("%.6f\n",cost_apm);
fclose(stdout);
}
int main()
{
citeste();
kruskal();
afiseaza();
return 0;
}