【Description】
Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。
【题解】
新建一个节点0，把各个点与0点连边，边权为在该点上建水库的代价
然后跑一边最小生成树就行了
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=400,maxm=200010; 5 int n,fa[maxn],tot=0,num=0; 6 long long ans=0; 7 struct edge{int x,y,w;}e[maxm]; 8 void read(int &k){ 9 k=0; int f=1; char c=getchar(); 10 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 11 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 12 k*=f; 13 } 14 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} 15 bool cmp(edge a,edge b){return a.w<b.w;} 16 int main(){ 17 read(n); for (int i=0;i<=n;i++) fa[i]=i; 18 for (int i=1;i<=n;i++)e[++tot].x=i,e[tot].y=0,read(e[tot].w); 19 for (int i=1;i<=n;i++) 20 for (int j=1;j<=n;j++)e[++tot].x=i,e[tot].y=j,read(e[tot].w); 21 sort(e+1,e+1+tot,cmp); 22 for (int i,x,y=1;i<=tot;i++){ 23 if (find(x=e[i].x)!=find(y=e[i].y)){ 24 ans+=e[i].w; fa[find(x)]=find(y); num++; 25 } 26 if (num==n) break; 27 } 28 return printf("%lld ",ans),0; 29 }