bzoj3479[Usaco2014 Mar]Watering the Fields*

bzoj3479[Usaco2014 Mar]Watering the Fields

题意：

草坪上有N个水龙头，修剪两个水管费用为欧几里得距离的平方。修水管的人只愿意修费用大于等于c的水管，问将水龙头联通的最小总费用。N≤2000

题解：

最小生成树。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 2010
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch=getchar(); int f=1,x=0;
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
12     return f*x;
13 }
14 int x[maxn],y[maxn],n,c,fa[maxn],cnt,ans;
15 struct e{int f,t,w;}; e es[maxn*maxn]; int ess;
16 inline bool cmp(const e& a,const e& b){return a.w<b.w;}
17 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
18 inline int sqr(int x){return x*x;}
19 int main(){
20     n=read(); c=read(); inc(i,1,n)x[i]=read(),y[i]=read();
21     inc(i,1,n)inc(j,i+1,n){int a=sqr(x[i]-x[j])+sqr(y[i]-y[j]); if(a>=c)es[++ess]=(e){i,j,a};}
22     sort(es+1,es+1+ess,cmp); inc(i,1,n)fa[i]=i;
23     inc(i,1,ess){
24         int x=find(es[i].f),y=find(es[i].t); if(x!=y)fa[y]=x,cnt++,ans+=es[i].w;
25         if(cnt==n-1)break;
26     }
27     if(cnt==n-1)printf("%d",ans);else printf("-1"); return 0;
28 }

20160810