描述 Description
农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000
输入格式 Input Format
第一行： 农场的个数，N（3<=N<=100）。
第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。
输出格式 Output Format
只有一个输出，其中包含连接到每个农场的光纤的最小长度。
样例输入 Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
样例输出 Sample Output
28
这道题直接从第一个点开始作为光纤的起点链接每一个牧场，然后记录在哪个牧场时所用光纤最短。
然后使用prim算法，现将第一个牧场添加进入到图中，然后枚举每条边，寻找现在能到达的边中的最短的那条。
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iomanip>
using namespace std;
int a[][];
int dis[];
bool vis[];
int main()
{
int n;
cin>>n;
memset(a,,sizeof(a));
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
cin>>a[i][j];
}
}
int minn1=,sum,sumn;
for(int k=;k<=n;k++)
{
memset(dis,,sizeof(dis));
for(int i=;i<=n;i++)
dis[i]=a[k][i];
memset(vis,,sizeof(vis));
vis[k]=;
sumn=;sum=;
for(int i=;i<=n;i++)
{
int minn=a[][],c=;
for(int j=;j<=n;j++)
if((!vis[j])&&(dis[j]<minn))
{
minn=dis[j];
c=j;
}
vis[c]=;
sumn+=minn;
for(int j=;j<=n;j++)
{
if((a[c][j])<dis[j]&&(!vis[j]))
dis[j]=a[c][j];
} }
for(int j=;j<=n;j++)
{
sum+=dis[j];
}
if(sum<minn1)
{
minn1=sum;
}
}
cout<<sum<<endl;
return ;
}
其实sumn这个变量记录的就是从起始点牧场到达各个牧场的最短距离，枚举完后sumn=sum的。
Watering Hole
题目：
Farmer John希望把水源引入他的N (1 <= N <= 300) 个牧场,牧场的编号是1~N.他将水源引入某个牧场的方法有两个,一个是在牧场中打一口井,另一个是将这个牧场与另一个已经有水源的牧场用一根管道相连.
在牧场i中打井的费用是W_i (1 <= W_i <= 100000).
把牧场i和j用一根管道相连的费用是P_ij (1 <= P_ij <= 100000, P_ij = P_ji, P_ii = 0).
请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源.
输入格式 Input Format
* 第1行: 一个正整数N.
* 第2~N+1行: 第i+1行包含一个正整数W_i.
* 第N+2~2N+1行: 第N+1+i行包含N个用空格分隔的正整数,第j个数表示P_ij.
输出格式 Output Format
总共有四个牧场.在1号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要3的费用.在不同的牧场间建立管道需要2,3或4的费用.
样例输入 Sample Input
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
样例输出 Sample Output
9
输出数据解释 Farmer John需要在4号牧场打一口井,然后把所有牧场都用管道连到1号牧场上,总共的花费是3+2+2+2=9.
时间限制 Time Limitation 1s
这道题直接直接从打井花费最少的地方开始打井，然后让用管子讲打井的牧场和其他牧场连通，比如：你在i花费3打了一口井要连到j牧场，连到j牧场要花费6，而在j牧场打一口井只用花费4，那就用在j牧场打井代替连接i到j，这样才会使花费最少.最后还是用Prim算法进行求最少花费。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int a[][];
int dis[];
bool vis[];
int sumn;
int main()
{
//freopen("add.in","r",stdin);
//freopen("add.out","w",stdout);
memset(vis,false,sizeof(vis));
memset(dis,,sizeof(dis));
int n;
memset(a,,sizeof(a));
cin>>n;
int minn1=,s;
for(int i=;i<=n;i++)
{
cin>>dis[i];
if(dis[i]<minn1)
{
minn1=dis[i];
s=i;
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
cin>>a[i][j];
}
}
sumn=;
sumn+=dis[s];
for(int i=;i<=n;i++)
{
if(dis[i]>a[s][i])
dis[i]=a[s][i];
}
vis[s]=;
for(int i=;i<=n;i++)
{
int minn=,c=;
for(int j=;j<=n;j++)
if((!vis[j])&&(dis[j]<minn))
{
minn=dis[j];
c=j;
}
vis[c]=;
sumn+=minn;
for(int j=;j<=n;j++)
{
if((a[c][j]<dis[j])&&(!vis[j]))
{
dis[j]=a[c][j];
}
}
}
cout<<sumn<<endl;
return ;
}