题解 p1550 [usaco08oct]打井watering hole

using namespace std;
struct {
    int u,v,d;
}a[3000000];
int cnt,x,n,m,ed,ans,f[400000];
bool cmp(node a,node b){
    return a.d<b.d;
}
int find(int k){
    return (f[k]==k)?k:(f[k]=find(f[k]));
}
void bing(int x,int y,int d){
    int u=find(x),v=find(y);
    if (u==v)return;
    f[u]=v;
    ans+=d;
    ++ed;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=300000;i++)f[i]=i;
    for (int i=1;i<=n;i++){
        scanf("%d",&x);
        a[++cnt].v=i;a[cnt].d=x;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            scanf("%d",&x);
            if (j<i)
                a[++cnt].u=j,a[cnt].v=i,a[cnt].d=x;
        }
    sort(a+1,a+1+cnt,cmp);
    for (int i=1;i<=cnt&&ed<=2*n+1;i++)
        bing(a[i].u,a[i].v,a[i].d);
    printf("%d",ans);
}