UVa 10397: Connect the Campus

在我的最小生成树的Prim算法的模板 基础上增加一个vis数组用于区分节点是否已加入集合T中。这里不能使用节点的min_dis为0作为该节点是否加入T中，因为题目中给出了已经相连的边，而我们将其权值设为了0，需要另加数组判断。

另一个注意点是这里Prim不一定需要执行循环N-1次，同样因为有边权初始化为0。及时终止循环可以稍微提高效率。

我的解题代码如下：

 #include    
#include    
#include    
#include    
#include    
#include    
#include    
  
using namespace std;  
  
#define Distance double   
#define INF 1000000   
#define MAXN 750   
double x[MAXN],y[MAXN];  
Distance dis[MAXN][MAXN];  
Distance min_dis[MAXN];  
//int nearest_v[MAXN];   
int vis[MAXN];  
  
Distance Prim(int v0, int N)  
{  
    //init   
    for(int i=0; i min_dis[i])   
            {  
                md = min_dis[i];  
                nv = i;  
            }  
        }  
  
        total_dis += md;  
        min_dis[nv] = 0;  
        vis[nv] = 1;  
  
        for(int i=0; i dis[i][nv])  
            {  
                min_dis[i] = dis[i][nv];  
//              nearest_v[i] = nv;   
            }  
        }  
        int ok = 0;  
        for(int i=0; i> N)  
    {  
        for(int i=0; i> M;  
        int na,nb;  
        for(int i=0; i