Farmer John 决定给他分别用 11 到 N(1 leq N leq 300)N(1≤N≤300) 分别编号的牧草浇水，他可以直接在一颗牧草旁边直接挖一口井来获得水，也可以用管子从任意有水的牧草那里来获得水。
在第 ii 颗牧草旁边挖一口井的代价为 W_i(1 leq W_i leq 100,000)Wi(1≤Wi≤100,000)，用管子连接第 ii 与第 jj 颗牧草的代价为 P_{ij}(1 leq P_{ij} leq100000,P_{ij} = P_{ji}; P_{ii}=0)Pij(1≤Pij≤100000,Pij=Pji;Pii=0)
请求出Farmer John浇灌这些牧草花费的最小代价。
__________________________________
比较简单！prim
建立超级源点，从超级源点向所有点连边，权为打井的花费。另外建图，求最小生成树！
__________________________________
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=305; 4 int mp[maxn][maxn]; 5 bool bz[maxn]; 6 int dis[maxn]; 7 int n,ans; 8 void prim(int u) 9 { 10 memset(dis,0x7f,sizeof dis); 11 dis[u]=0; 12 for(int i=1;i<=n+1;++i) 13 { 14 int mn=0x7f7f7f7f,no=0; 15 for(int j=1;j<=n+1;++j) 16 if(bz[j]==0&&dis[j]<mn)no=j,mn=dis[j]; 17 ans+=dis[no]; 18 bz[no]=1; 19 for(int j=1;j<=n+1;++j) 20 if(bz[j]==0&&mp[no][j]<dis[j]&&no!=j)dis[j]=mp[no][j]; 21 } 22 } 23 int main() 24 { 25 scanf("%d",&n); 26 for(int x,i=1;i<=n;++i) 27 { 28 scanf("%d",&x); 29 mp[n+1][i]=mp[i][n+1]=x; 30 } 31 for(int i=1;i<=n;++i) 32 for(int j=1;j<=n;++j) 33 { 34 scanf("%d",&mp[i][j]); 35 mp[j][i]=mp[i][j]; 36 } 37 prim(n+1); 38 cout<<ans<<endl; 39 return 0; 40 }