ZJNU 1213 – 取水——高级

某个村庄i可以打一口井取水花费费用Wi，也可以与有水的村庄连接取水

又因为不可能没有一个村庄不打井（即至少有一个村庄打井，其余村庄连向它）

实际上就可以理解为，将水井看作第N+1个村庄，需要有村庄与这个N+1村庄相连，才能保证所有村庄有水

而村庄i连接到村庄N+1的费用，就可以直接理解为打井的费用Wi

其余部分使用Kruskal最小生成树即可

#include<cstdio>
#include<algorithm>
using namespace std;
struct tube{
    int from,to,cost;
    bool operator < (const tube &a) const{
        return cost<a.cost;
    }
}p[];
int gp[];
int find(int a){
    return a==gp[a]?a:(gp[a]=find(gp[a]));
}
int main(){
    int i,j,N,d,cnt=,k=,sum;
    scanf("%d",&N);
    for(i=;i<=N;i++){
        scanf("%d",&d);
        p[cnt].from=i;
        p[cnt].to=N+;
        p[cnt++].cost=d;
        gp[i]=i;
    }
    for(i=;i<=N;i++)
        for(j=;j<=N;j++){
            scanf("%d",&d);
            if(i==j)
                continue;
            p[cnt].from=i;
            p[cnt].to=j;
            p[cnt++].cost=d;
        }
    sort(p,p+cnt);
    for(sum=i=;i<cnt;i++){
        if(k==N)
            break;
        if(find(p[i].from)!=find(p[i].to)){
            gp[find(p[i].to)]=find(p[i].from);
            sum+=p[i].cost;
            k++;
        }
    }
    printf("%d\n",sum);    return ;
}