原题链接

题解

思维转换，想象井里的水都来自山上，并把山看成一个点，那么这道题就变成了最小生成树
简证最小生成树原理：
按边权排序，然后遍历，如果这条边的两个点之前每连过，那么就连上，因为这就是这两个点所在集合之间的最短路径了，不然这条边没必要加，因为已经联通了

算是一种贪心？

code

#include<bits/stdc++.h>
using namespace std;
struct unit
{
    int x,y,val;
    bool operator<(const unit &b) const {return b.val<val;}
};

int fa[305]={0};
int finds(int now){return (fa[now]==now?now:finds(fa[now]));}

int main()
{
    int n,x;
    cin>>n;

    priority_queue<unit> q;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        fa[i]=i;
        q.push({0,i,x});
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>x;
            if(j<i) q.push({i,j,x});
        }
    }

    int ans=0;
    while(q.size())
    {
        int x=q.top().x,y=q.top().y,v=q.top().val;
        q.pop();

        if(finds(x)!=finds(y))
        {
            fa[finds(x)]=finds(y);
            ans+=v;
        }
    }

    cout<<ans;
    return 0;
}