UVa 10397: Connect the Campus

在我的最小生成樹的Prim算法的模板 基礎上增加一個vis數組用於區分節點是否已加入集合T中。這裡不能使用節點的min_dis為0作為該節點是否加入T中，因為題目中給出了已經相連的邊，而我們將其權值設為了0，需要另加數組判斷。

另一個注意點是這裡Prim不一定需要執行循環N-1次，同樣因為有邊權初始化為0。及時終止循環可以稍微提高效率。

我的解題代碼如下：

 #include <iostream>   
#include <cstdio>   
#include <cstring>   
#include <cmath>   
#include <cstdlib>   
#include <string>   
#include <algorithm>   
  
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<N; i++)  
    {  
        min_dis[i] = dis[i][v0];  
//      nearest_v[i] = v0;   
    }  
    min_dis[v0] = 0;  
    memset(vis,0,sizeof(vis));  
    vis[v0] = 1;  
    Distance total_dis = 0;  
    for(int k=1; k<N; k++)  
    {  
        Distance md = INF;  
        int nv = v0;  
        for(int i=0; i<N; i++) if(!vis[i])  
        {  
            if(md > min_dis[i])   
            {  
                md = min_dis[i];  
                nv = i;  
            }  
        }  
  
        total_dis += md;  
        min_dis[nv] = 0;  
        vis[nv] = 1;  
  
        for(int i=0; i<N; i++) if(!vis[i])  
        {  
            if(min_dis[i] > dis[i][nv])  
            {  
                min_dis[i] = dis[i][nv];  
//              nearest_v[i] = nv;   
            }  
        }  
        int ok = 0;  
        for(int i=0; i<N; i++) if(min_dis[i]!=0) { ok=1; break; }  
        if(!ok) break;  
    }  
    return total_dis;  
}  
int main()  
{  
    int N,M;  
    while(cin >> N)  
    {  
        for(int i=0; i<N; i++)  
        {  
            scanf("%lf %lf",&x[i],&y[i]);  
            for(int j=0; j<=i; j++)    
                dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));    
        }  
        cin >> M;  
        int na,nb;  
        for(int i=0; i<M; i++)  
        {  
            scanf("%d %d",&na,&nb);  
            dis[na-1][nb-1]=dis[nb-1][na-1]=0;  
        }  
        printf("%.2lf\n", Prim(0,N));  
    }  
    return 0;  
}