HDU1875 畅通工程再续（最小生成树）

题目链接

水题

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;
const int MAXM = 10000;
int F[MAXN];

struct Point{
    int x, y;
}p[MAXN];

struct Edge{
    int u, v;
    double w;
}edge[MAXM];
int tol;
double dis(Point a, Point b){
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
void addedge(int u,int v,double w){
    edge[tol].u = u;
    edge[tol].v = v;
    edge[tol++].w = w;
}
bool cmp(Edge a,Edge b){
    return a.w < b.w;
}
int findfa(int x){
    if(F[x] == -1)return x;
    else return F[x] = findfa(F[x]);
}
double Kruskal(int n){
    memset(F, -1, sizeof(F));
    sort(edge, edge+tol, cmp);
    int cnt = 0;
    double ans = 0;
    for(int i = 0; i < tol; i++){
        int u = edge[i].u;
        int v = edge[i].v;
        double w = edge[i].w;
        int t1 = findfa(u);
        int t2 = findfa(v);
        if(t1 != t2){
            ans += w;
            F[t1] = t2;
            cnt++;
        }
        if(cnt == n-1)break;
}
    if(cnt < n-1)return -1;
    else return ans;
}


int main(){
//    freopen("a.txt", "r", stdin);
    int n, t; cin >> t;
    while(t--){
        tol = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%d %d", &p[i].x, &p[i].y);
        }
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                double d = dis(p[i], p[j]);
                if(d >= 10 && d <= 1000){
                    addedge(i, j, d);
                }
            }

        }
        double ans = Kruskal(n)*100;
        if(ans == -100) cout << "oh!" << endl;
        else printf("%.1f\n", ans);
    }
    return 0;
}