HDU 1162 Eddy's Picture - Prim 最小生成樹模板題

題目大意

給定 n 個點座標，邊權為歐氏距離。求連通所有點的最小總邊長（MST）。多測試案例，n ≤ 100。

Prim 算法 O(n²) 實現

1. 預計算距離矩陣 dist[i][j]。
2. low[i] 存儲點 i 到當前樹的最短距離。
   vis[i] 標記是否已入樹。
3. 從 1 開始，重複 n-1 次：選未入樹且 low 最小的點 u，加入樹，累加 low[u]，更新鄰居 low[v]=min(low[v], dist[u][v])。

完整代碼

#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 110
#define INF 1e9
struct Point { double x, y; } p[MAXN];
double dist[MAXN][MAXN], low[MAXN];
int vis[MAXN], n;

void prim() {
    memset(vis, 0, sizeof(vis));
    int u = 1; vis[u] = 1;
    for(int i=1;i<=n;i++) if(i!=u) low[i]=dist[u][i];
    double ans = 0;
    for(int i=1;i