Pagini recente » Cod sursa (job #472771) | Cod sursa (job #2574458)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
ifstream f("desen.in");
ofstream g("desen.out");
const int NMax = 400005;
pair <int,int> P[NMax];
int N, M, Total, TT[NMax], k, RG[NMax],nr,kk;
struct Edge
{
int x,y,c;
}V[NMax];
struct Point
{
int x,y;
}puncte[NMax];
bool Compare(Edge a, Edge b)
{
return a.c < b.c;
}
void Read()
{
f>> N;
for(int i = 1; i <= N; i++)
{
f >> V[i].x >> V[i].y>>V[i].c;
}
sort(V+1, V+N+1, Compare);
}
int Find(int nod)
{
while(TT[nod] != nod)
nod = TT[nod];
return nod;
}
void Unite(int x, int y)
{
if(RG[x] < RG[y])
TT[x] = y;
if(RG[y] < RG[x])
TT[y] = x;
if(RG[x] == RG[y])
{
TT[x]=y;
RG[y]++;
}
}
void Solve()
{
for(int i=1;i<=nr;i++)
{
if(Find(V[i].x) != Find(V[i].y))
{
Unite(Find(V[i].x), Find(V[i].y));
P[++k].first = V[i].x;
P[k].second = V[i].y;
Total += V[i].c;
}
}
}
int main()
{
f>>N;int j;
for(int i = 1; i <= N; i++)
{ k=0;Total=0;
f>> puncte[i].x >> puncte[i].y;
for(j=1;j<i;j++)
{
kk++;
V[kk].x=i;
V[kk].y=j;
V[kk].c=sqrt(abs(puncte[i].x - puncte[j].x) * abs(puncte[i].x - puncte[j].x) + abs(puncte[i].y - puncte[j].y) * abs(puncte[i].y - puncte[j].y));
}
sort(V+1, V+kk+1, Compare);
nr=kk;
kk=0;
for(int j = 1; j <= nr; i++)
{
TT[j]=j;
RG[j]=1;
}
Solve();
g << Total << "\n";
}
return 0;
}