本文共 1002 字，大约阅读时间需要 3 分钟。

所以到底读“给予”的“给”，还是平时用的“给”。。。

FJ决定给N(1<=N<=300)个草地给水，草地编号为1到N。他可以在该草地处建立一口井，也可以建立管道从别的草地引水进来，在第i块草地处挖一口井需要花费W_i(1<=W_i<=100,000)，连接井i和井j的管道需要花费P_ij(1<=P_ij<=100,000,P_ij=P_ji;P_ii=0)。

Input

第一行，一个整数N

Output

输出最少花费。

Sample Input

4

Sample Output

9

最小生成树之前是学过的。然后看到这题第一感觉就是最小生成树。但是使此节点生效的话需要一个“启动值”，然后就感觉有点麻烦。我试想过将路径加上初始值，但是貌似不可行。直到评讲时——

#include
   
    int n,f[301][301],k,ans;bool b[301];int main(){   	freopen("water.in","r",stdin);	freopen("water.out","w",stdout); 	scanf("%d",&n);	for(int i=1;i<=n;++i)  //读入距离	  scanf("%d",&f[0][i]);	for(int i=1;i<=n;++i)	  for(int j=1;j<=n;++j) 	     scanf("%d",&f[i][j]);	k=n;b[0]=1;	while(k--){      //处理n次，将n个节点全都接上水		int min=100000,d;		for(int i=0;i<=n;++i)  //寻找一个已接上水的节点		  if(b[i]==1)		    for(int j=1;j<=n;++j)  //寻找一个没接上水的节点		      if(b[j]==0&&f[i][j]