BZOJ 3479 [Usaco2014 Mar]Watering the Fields灌溉

题目大意

给你一堆点，求每一条边都大于c的最小费用生成树。

直接上Kruskal就可以了，裸题。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,c,x[2010],y[2010],fa[2010],cnt,tot;
long long ans;
struct edge
{
    int from,to,val;
}e[5000010];
bool cmp(edge tx,edge ty) {return tx.val<ty.val;}
int unifind(int tx) {return fa[tx]==tx?tx:fa[tx]=unifind(fa[tx]);}
inline int cf(int tx) {return tx*tx;}
inline void addedge(int tx,int ty,int tz) {e[++tot].to=ty,e[tot].from=tx,e[tot].val=tz;}
inline int getdis(int tx,int ty) {return cf(x[tx]-x[ty])+cf(y[tx]-y[ty]);}
void kruskal()
{
    sort(e+1,e+tot+1,cmp);
    for(int i=1;i<=tot;++i)
    {
        int tx=unifind(e[i].from),ty=unifind(e[i].to);
        if(tx!=ty)
        {
            fa[tx]=ty;
            ++cnt;
            ans+=e[i].val;
            if(cnt==n-1) return;
        }
    }
    if(cnt<n-1) ans=-1;
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;++i) scanf("%d%d",x+i,y+i);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            double tmp=getdis(i,j);
            if(tmp>=c) addedge(i,j,tmp);
        }
    kruskal();
    printf("%lld\n",ans);
}