求最小生成树（prim算法）

Prim算法是一种求解最小生成树的贪心算法，具体步骤如下：

1. 选择一个起点，将其加入最小生成树中。

2. 对于从起点所连接的所有边，将其加入一个优先队列中，以边权值为关键字进行排序。

3. 取出队列中权值最小的边，如果该边的终点不在最小生成树中，则将该边加入最小生成树，并将该点加入最小生成树中。

4. 重复步骤2和3，直到最小生成树中包含了所有的点。

下面是C++代码实现：

const int INF = 0x3f3f3f3f;
const int MAXN = 1000;
int n, m; // n为点数，m为边数
int vis[MAXN]; // vis[i]表示i是否在最小生成树中
int dis[MAXN]; // dis[i]表示i到最小生成树的距离
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], val[MAXN * 2], cnt; // 存储图

void add(int x, int y, int z) {
    nxt[++cnt] = head[x];
    to[cnt] = y;
    val[cnt] = z;
    head[x] = cnt;
}

int prim() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    int ans = 0;
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (!u || dis[j] < dis[u])) {
                u = j;
            }
        }
        vis[u] = true;
        ans += dis[u];
        for (int j = head[u]; j; j = nxt[j]) {
            int v = to[j];
            if (!vis[v] && val[j] < dis[v]) {
                dis[v] = val[j];
            }
        }
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    printf("%d\n", prim());
    return 0;
}

其中，add(x, y, z)用于存储无向图的边，dis[i]表示点i到最小生成树的距离，vis[i]表示i是否在最小生成树中。函数prim()返回最小生成树的权值和。