首页 > 代码库 > UVA 10034 Freckles

UVA 10034 Freckles

MST直接上代码了

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 110int p[MAXN],N,cas;int Find(int x) {return p[x] == x ? x : p[x] = Find(p[x]);}struct dis{    int u,v;    double dist;    friend bool operator < (const dis &a,const dis &b)    {        return a.dist < b.dist;    }}d[MAXN * MAXN];struct node{    double x,y;}src[MAXN];void init(){    scanf("%d",&N);    for (int i = 1; i <= N; i++) scanf("%lf%lf",&src[i].x,&src[i].y);    cas = 0;    for (int i = 1; i <= N; i++)        for (int j = i + 1; j <= N; j++)     {        d[cas].u = i; d[cas].v = j;        //printf("%lf %lf %lf %lf\n",src[i].x,src[j].x,src[i].y,src[j].y);        d[cas++].dist = sqrt((src[j].x - src[i].x) * (src[j].x - src[i].x) + (src[j].y - src[i].y) * (src[j].y - src[i].y));     }    sort(d,d + cas);}double kruskal(){    double ans = 0;    //for (int i = 0; i < cas; i++) printf("%d %d %2.lf\n",d[i].u,d[i].v,d[i].dist);    for (int i = 0; i <= N; i++) p[i] = i;    for (int i = 0; i < cas; i++)    {        int  u = d[i].u, v = d[i].v;        double w = d[i].dist;        //printf("%.2lf\n",w);        int  x = Find(u) , y = Find(v);        if (x != y)        {            //printf("%.2lf\n",w);            ans += w;            p[x] = y;        }    }    return ans;}int main(){    int T;    scanf("%d",&T);    while (T--)    {        init();        double ans = kruskal();        printf("%.2f\n",ans);        if (T) putchar(\n);    }    return 0;}

 

UVA 10034 Freckles