Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000). Each field i is described by a distinct point (xi, yi) in the 2D plane,with 0 <= xi, yi <= 1000. The cost of building a water pipe between two fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his fields are linked together -- so that water in any field can follow a sequence of pipes to reach any other field.Unfortunately, the contractor who is helping FJ install his irrigation system refuses to install any pipe unless its cost (squared Euclidean

length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all his fields with a network of pipes.

給定 n 個點，第 i 個點的坐標為 (xi?,yi?)，如果想連通第 i 個點與第 j 個點，需要耗費的代價為兩點的距離。第 i 個點與第 j 個點之間的距離使用歐幾里得距離進行計算，即：

(xi??xj?)^2+(yi??yj?)^2

我們規定耗費代價小于 c 的兩點無法連通，求使得每兩點都能連通下的最小代價，如果無法連通輸出 -1。

* Line 1: The integers N and C.

* Lines 2..1+N: Line i+1 contains the integers xi and yi.

第一行兩個整數 n,cn,c 代表點數與想要連通代價不能少于的一個數。
接下來 n 行每行兩個整數 xi?,yi? 描述第 i 個點。

* Line 1: The minimum cost of a network of pipes connecting the

fields, or -1 if no such network can be built.

一行一個整數代表使得每兩點都能連通下的最小代價，如果無法連通輸出 -1。

INPUT DETAILS:

There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11.

OUTPUT DETAILS:

FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore builds a pipe between (0,2) and (5,0) at cost 29, and a pipe between (0,2) and (4,3) at cost 17.

Source: USACO 2014 March Contest, Silver

數據規模與約定

對于 100% 的數據，1≤n≤2000，0≤xi?,yi?≤1000，1≤c≤10^6。

題目分析：

這是一道prim算法題，我們可以利用prim算法的模板，加上題目的限制條件兩點距離不得小于c，就可以解出該題。

話不多說直接上代碼吧

#include<iostream>
#include<cmath>
using namespace std;
const int N=2005;
const int INF=1e8;
int n,c;
struct Node{
    int x,y;
}node[N];
int g[N][N];//每個點之間的距離
int dist[N];
bool st[N];
int distance(int x1,int y1,int x2,int y2){
    int t=pow((x1-x2),2)+pow((y1-y2),2);
    return t;
}

int Prim(){
    int res=0;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            int x1=node[i].x,y1=node[i].y,x2=node[j].x,y2=node[j].y;
            int t=distance(x1,y1,x2,y2);
            if(t>=c)g[i][j]=g[j][i]=t;
            else g[i][j]=g[j][i]=INF;
        }
    }
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=0;j<n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
        }
        if(i&&dist[t]==INF)return -1;
        if(i)res+=dist[t];
        st[t]=true;
        for(int j=1;j<n;j++)
            dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

int main()
{   
    cin>>n>>c;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        node[i]={x,y};
        dist[i]=INF;
        g[i][i]=INF;
    }
    int res=Prim();
    cout<<res;
    return 0;
}

2021-08-03

20:43:34