晚上闲游洛谷，偶然发现这道绿色的MST板子
首先，毫无疑问，这是一道MST的题，而重点在与这句话：“请求出农民John 需要为使所有农场都与有水的农场相连或拥有水井所需要的钱数。”
需要让所有地方都有水，但是这些农场最开始是没水的，我们需要加入一个“水源”节点，而0号节点一般在MST板子中不会有用，这成为了我们最好的选择（如果你强迫症打MST从0号到n-1号节点那你就当我什么都没说）
我们只需要让0号节点也加入进来并把MST的条件设为n条边即可，其他剩下的地方直接套MST板子，我就不打算法步骤了（其实是因为懒）
参考程序如下：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 struct node 5 { 6 int u,v,w; 7 }; 8 node f[100001]; 9 int n,w,parent[305],sum,num,weight; 10 bool cmp(node a,node b){return a.w<b.w;} 11 int find(int x) 12 { 13 if(parent[x]==x)return x; 14 return parent[x]=find(parent[x]); 15 } 16 void Union(int u,int v) 17 { 18 int U=find(u),V=find(v); 19 if(U==V)return; 20 parent[U]=V; 21 } 22 int main() 23 { 24 cin>>n; 25 for(int i=0;i<=n;i++) 26 { 27 parent[i]=i; 28 } 29 for(int i=1;i<=n;i++) 30 { 31 cin>>w; 32 f[++sum].u=0; 33 f[sum].v=i; 34 f[sum].w=w; 35 } 36 for(int i=1;i<=n;i++) 37 { 38 for(int j=1;j<=n;j++) 39 { 40 cin>>w; 41 if(i>j) 42 { 43 f[++sum].u=i; 44 f[sum].v=j; 45 f[sum].w=w; 46 } 47 } 48 } 49 sort(f+1,f+1+sum,cmp); 50 for(int i=1;i<=sum;i++) 51 { 52 int u=find(f[i].u),v=find(f[i].v); 53 if(u!=v) 54 { 55 weight+=f[i].w; 56 num++; 57 Union(u,v); 58 } 59 if(num==n)break; 60 } 61 cout<<weight<<endl; 62 return 0; 63 }