Cod sursa(job #657534)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 6 ianuarie 2012 18:44:00
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 4000001
using namespace std;

ifstream f("retea2.in");
ofstream g("retea2.out");

struct poz {
    int xp,yp;
};
float cost(poz a,poz b) {
    float r;
    r=(a.xp-b.xp)*(a.xp-b.xp)+(a.yp-b.yp)*(a.yp-b.yp);
    r=(float)sqrt((float)r);
    return r;
}
poz bl[3000],ct[3000];
int n,m,i,j;
int M;
float ANS=0;
int X[NMAX],Y[NMAX],GR[NMAX],I[NMAX];
float C[NMAX];
bool comp(int a,int b) {
    return(C[a]<C[b]);
}

int rad(int x) {
    int p,y;
    for (p=x;p!=GR[p];p=GR[p]);
    for (;x!=GR[x];) {
        y=GR[x];
        GR[x]=p;
        x=y;
    }
    return p;
}
void unite(int x,int y) {
    GR[y]=x;
}

int main () {
    f >> n >> m;
    for (i=1;i<=n;i++) f >> ct[i].xp >> ct[i].yp;
    for (i=1;i<=m;i++) f >> bl[i].xp >> bl[i].yp;
    for (i=1;i<=m;i++)
        for (j=i+1;j<=m;j++) {
            ++M;
            X[M]=i;Y[M]=j;C[M]=cost(bl[i],bl[j]);I[M]=M;
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++) {
            X[M+j]=0;Y[M+j]=j;I[M+j]=M+j;
            if (C[M+j]==0) C[M+j]=cost(bl[j],ct[i]);
                      else C[M+j]=min(C[M+j],cost(bl[j],ct[i]));
        }
    M=M+m;
    sort(I+1,I+M+1,comp);
    for (i=0;i<=m;i++) GR[i]=i;
    for (i=1;i<=M;i++)
        if(rad(X[I[i]])!=rad(Y[I[i]])) {
            ANS+=C[I[i]];
            unite(rad(X[I[i]]),rad(Y[I[i]]));
        }
    g << fixed;
    g << setprecision(6) << ANS << '\n';
    f.close();g.close();
    return 0;
}