（紀中）1930. 灌溉農田（irrigation）【最小生成樹】

*(File IO): input:irrigation.in output:irrigation.out

時間限制: 1000 ms 空間限制: 128000 KB 具體限制

題目描述

由于最近缺少降雨，農夫約翰決定在他的N塊農田之間建立一個供水管網。每塊的位置可以用一個二維坐标來表示 （ x i , y i ） （xi,yi） （xi,yi），在第i塊地和第j塊地之間修建一個管道的話，代價是 ( x i − x j ) 2 + ( y i − y j ) 2 (xi - xj)^2 + (yi - yj)^2 (xi−xj)2+(yi−yj)2。農夫約翰想要建立一個花費代價最小的供水管網，使得他所有的地都能被連接配接在一起（使得水能夠通過一系列的管道流到各個田地裡去）。不幸的是，建造管道的人拒絕建造花費代價小于C的單條管道。請幫助約翰計算最少需要花費多少代價，才能建成這個供水管網。

輸入

第一行是兩個正整數 N N N和 C C C。

第 2 2 2行到第 N + 1 N+1 N+1行，每行兩個整數，表示 x i xi xi和 y i yi yi。

輸出

輸出建立供水管網的最小代價，如果不能建立供水管網，就輸出 − 1 -1 −1。

樣例輸入

3 11

0 2

5 0

4 3

樣例輸出

46

資料範圍限制

1 < = N < = 2000 , 0 < = x i , y i < = 1000 1<=N<=2000,0<=xi,yi<=1000 1<=N<=2000,0<=xi,yi<=1000。

提示

樣例中，約翰不能在 （ 4 , 3 ） （4,3） （4,3）和 （ 5 , 0 ） （5,0） （5,0）之間建立管道，因為這個管道的代價是 10 10 10。是以，他隻能在 （ 0 , 2 ） （0,2） （0,2）和 （ 5 , 0 ） （5,0） （5,0）之間修建一條管道，花費是 29 29 29，在 （ 0 , 2 ） （0,2） （0,2）和 （ 4 , 3 ） （4,3） （4,3）之間修建一條管道，花費是 17 17 17，是以總的最小花費是 29 + 17 = 46 29+17=46 29+17=46。

解題思路

這道題就是一道最小生成樹，可以采用普裡姆算法.

代碼

#include<bits/stdc++.h>
using namespace std;
int n,c,x[2020],y[2020],a[2020][2020],v[2020],b[2020],minn,k,ans;
int main()
{
	freopen("irrigation.in","r",stdin);
    freopen("irrigation.out","w",stdout);
    scanf("%d%d",&n,&c);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            a[i][j]=999999999;
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        for(int j=1; j<=i-1; j++)
            if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])>=c)
                a[i][j]=a[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
    }
    v[1]=1;
    for(int i=2; i<=n; i++)
        b[i]=a[1][i];
    for(int j=1; j<=n-1; j++)
    {
        minn=999999998;
        for(int j=1; j<=n; j++)
            if(v[j]==0&&b[j]<=minn)
            {
                minn=b[j];
                k=j;
            }
        v[k]=1;
        ans+=b[k];
        for(int j=1; j<=n; j++)
            if(v[j]==0&&a[j][k]<=b[j])
                b[j]=a[j][k];
    }
    for(int i=1; i<=n; i++)
        if(!v[i])
        {
            printf("-1");
            return 0;
        }
    printf("%d",ans);
}