P1550 [USACO08OCT]打井Watering Hole 最小生成树

题目背景

John的农场缺水了！！！

题目描述

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).

Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water all of his pastures.

POINTS: 400

农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若

干井，并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。

请求出农民John 需要为使所有农场都与有水的农场相连或拥有水井所需要的钱数。

输入输出格式

输入格式：

第1 行为一个整数n。

第2 到n+1 行每行一个整数，从上到下分别为W_1 到W_n。

第n+2 到2n+1 行为一个矩阵，表示需要的经费（P_ij）。

输出格式：

只有一行，为一个整数，表示所需要的钱数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

9


建图非常的巧妙  
增加一个点(n+1)  为地下水点  每个点都有到这个点的花费(打井)
然后直接最小生成树即可

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
const int N=100001;
const int M=100000;
int pos;
struct Edge
{
    int u,v,val;
}edge[N];
void add(int a,int b,int c)
{
    edge[++pos]=Edge{a,b,c};
}
bool cmp(Edge a,Edge b)
{
    return a.val<b.val;
}
int f[N];
int find1(int x)
{
    return x==f[x]?x:f[x]=find1(f[x]);
}
void union1(int a,int b)
{
    int x=find1(a),y=find1(b);
    if(x!=y)
        f[x]=y;
}
int n,x,a,b,c,ans;
int main()
{
    RI(n);rep(i,1,n+1)f[i]=i;
    rep(i,1,n)
    {
        RI(x);add(i,n+1,x);
    }
    rep(i,1,n)
    rep(j,1,n)
    {
        RI(x);
        if(i!=j)
        add(i,j,x);
    }
    sort(edge+1,edge+1+pos,cmp);
    x=0;
    rep(i,1,pos)
    {
        a=find1(edge[i].u);b=find1(edge[i].v);
        if(a==b)continue;
        union1(a,b);
        ans+=edge[i].val;
        x++;
        if(x==n)break;
    }
    cout<<ans;
    return 0;
}

View Code