P1550 [USACO08OCT]打井Watering Hole （最小生成树+Prim算法）
John的农场缺水了！！！
Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.
Digging a well in pasture i costs W_i (1 <= W_i <= 100,000).
Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).
Determine the minimum amount Farmer John will have to pay to water all of his pastures.
POINTS: 400
农民John 决定将水引入到他的n(1<=n<=300)个牧场。他准备通过挖若
干井，并在各块田中修筑水道来连通各块田地以供水。在第i 号田中挖一口井需要花费W_i(1<=W_i<=100,000)元。连接i 号田与j 号田需要P_ij (1 <= P_ij <= 100,000 , P_ji=P_ij)元。
请求出农民John 需要为连通整个牧场的每一块田地所需要的钱数。
第1 行为一个整数n。
第2 到n+1 行每行一个整数，从上到下分别为W_1 到W_n。
第n+2 到2n+1 行为一个矩阵，表示需要的经费（P_ij）。
输出格式：只有一行，为一个整数，表示所需要的钱数。
输出样例#1：
9
说明
John等着用水，你只有1s时间！！！
将打井看成0结点，打井的花费就相当于0结点到各个结点的距离
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN=310; struct Node { int adjvex; int lowcost; }closedge[MAXN]; int cost[MAXN][MAXN]; int MinV_Ucost(int n) //这个函数是用来找V集合的点到U集合点的最短cost(当然是只有两个点） { int MINN=0x3f3f3f3f; int i,v; for(i=0;i<=n;i++) { if(closedge[i].lowcost!=0) //等于0的就已经进U集合了，不做考虑，这样避免了生成环。 { if(closedge[i].lowcost<MINN) { MINN=closedge[i].lowcost; v=i; } } } if(MINN==0x3f3f3f3f) { printf("不连通\n"); //原图不连通，至少有一个不为INF才连通啊 return 0; } else return v; } int Prim(int u,int n) //u是U集合的第一个点，可以认为假设 { int i,j; int v; int ans=0; closedge[u].lowcost=0; //=0就是将该结点放入U集合中 for(i=0;i<=n;i++) { if(i!=u) { closedge[i].adjvex=u; //i是在V集合中的点,同时说明第一个点是没有adjvex的 closedge[i].lowcost=cost[u][i]; } } for(j=0;j<n;j++) //第一个点已经确定，进入U，还剩n-1个点没进U集合 { v=MinV_Ucost(n); ans+=closedge[v].lowcost; /*u=closedge[v].adjvex; //这样就多了个可以输出两邻接点的功能 printf("%d %d\n",u,v);*/ closedge[v].lowcost=0; //把新点加入U集合。 for(i=0;i<=n;i++) //更新V各点到U各点的最短距离。 { if(cost[v][i]<closedge[i].lowcost) //在U中的点是0，所以if语句无视 { closedge[i].lowcost=cost[v][i]; closedge[i].adjvex=v; } } } return ans; } int main() { int n; scanf("%d",&n); int i,j; for(i=1;i<=n;i++) { scanf("%d",&cost[0][i]); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&cost[i][j]); printf("%d\n",Prim(0,n)); return 0; }