题目描述：
Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。
把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0).
计算Farmer John所需的最少代价。
题解：
最小生成树经典题。
我们建立一个超级源点，将每个点与超级源点建边，边权为每个点建立水库的费用。
接下来我们只需要在新图上做最小生成树即可。
附上代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<vector> using namespace std; int n,idx,ans,k,fa[1001]; bool vis[301][301]; struct Edge { int x,y,v; }f[100001]; bool cmp(const Edge &a,const Edge &b) { return a.v<b.v; } int find(int p) { if(fa[p]!=p) fa[p]=find(fa[p]); return fa[p]; } void merge(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) fa[fx]=fy; } int main() { scanf("%d",&n); for(int i=1;i<=n+1;i++) fa[i]=i; for(int i=1;i<=n;i++) { int a; scanf("%d",&a); f[++idx].x=i; f[idx].y=n+1; f[idx].v=a; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { int a; scanf("%d",&a); if(a==0||vis[i][j]==1) continue; f[++idx].x=i; f[idx].y=j; f[idx].v=a; vis[i][j]=vis[j][i]=1; } sort(f+1,f+idx+1,cmp); for(int i=1;i<=idx;i++) { if(find(f[i].x)!=find(f[i].y)) { merge(f[i].x,f[i].y); ans+=f[i].v; k++; } if(k==n) break; } printf("%d",ans); }