输入数据： 第一行。输出两个数。n和m。 后面有n行，对应着n条路径，每行三个值。前两个代表两个点，第三个表示两个点的距离。 m代表有m个点。求m个点的最小生成树的路径值。 输出数据: 一个数，为最少权值。

算法：Kruskal

Kruskal算法是一种常见的求最小生成树的贪心算法。具体思路是先将所有边按照权值从小到大排序，然后从小到大枚举每条边，如果这条边所连接的两个点不在同一个连通块中，则将这条边加入最小生成树中，同时将这两个点所在的连通块合并。

在实现时，可以使用并查集来维护连通块。

时间复杂度：O(mlogm)，其中m为边数。

Python 代码

相关问题

写出满足如下条件的C++代码：无优先级运算问题 输入格式: 第一行输入正整数n和整数m 第二行输入具体的n个正整数。 输出格式: 第一行输出最少运算次数。 第二行输出对应的运算表达式。若输入的n个正整数无法运算得到m，则输出“-1”。

以下是满足条件的C++代码：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 105;
int n, m, a[MAXN];
int dp[MAXN][MAXN][MAXN], pre[MAXN][MAXN][MAXN];

void print_expression(int l, int r, int v, vector<char>& op) {
    if (l == r) {
        cout << a[l];
        return;
    }
    int k = pre[l][r][v];
    if (k == -1) {
        cout << "(";
        print_expression(l, r - 1, v - a[r], op);
        cout << "+";
        print_expression(r, r, a[r], op);
        cout << ")";
    } else {
        cout << "(";
        print_expression(l, k, dp[l][r][v], op);
        for (int i = k + 1; i <= r; i++) {
            cout << op[i];
            if (i == r) {
                print_expression(i, i, a[i], op);
            } else {
                print_expression(i, r, v, op);
            }
        }
        cout << ")";
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    memset(dp, -1, sizeof(dp));
    dp[1][n][0] = 0;
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int v = 0; v <= m; v++) {
                if (dp[l][r][v] != -1) {
                    continue;
                }
                int res = -1;
                for (int k = l; k < r; k++) {
                    if (dp[l][k][v] != -1 && dp[k + 1][r][v] != -1) {
                        int cnt = dp[l][k][v] + dp[k + 1][r][v];
                        if (res == -1 || cnt < res) {
                            res = cnt;
                            pre[l][r][v] = k;
                        }
                    }
                    if (v >= a[r] && dp[l][r - 1][v - a[r]] != -1) {
                        int cnt = dp[l][r - 1][v - a[r]] + 1;
                        if (res == -1 || cnt < res) {
                            res = cnt;
                            pre[l][r][v] = -1;
                        }
                    }
                }
                dp[l][r][v] = res;
            }
        }
    }
    if (dp[1][n][m] == -1) {
        cout << "-1" << endl;
    } else {
        vector<char> op(n + 1);
        print_expression(1, n, m, op);
        cout << endl;
    }
    return 0;
}

该程序使用动态规划算法求解无优先级运算问题。具体来说，设 $dp[l][r][v]$ 表示区间 $[l,r]$ 内的数可以通过运算得到 $v$ 的最少运算次数。我们枚举 $[l,r]$ 以及 $v$，考虑如何转移。对于任意的 $l \leq k < r$，我们可以把区间 $[l,r]$ 拆成区间 $[l,k]$ 和 $[k+1,r]$ 两部分，分别计算它们得到的值，然后把它们合并起来。这样的话，合并操作需要进行一次加法运算，因此需要进行 $dp[l][k][v]$ 次运算和 $dp[k+1][r][v]$ 次运算。如果区间 $[l,r]$ 的最后一个数为 $a_r$，我们也可以把它拆分出来单独计算，这样需要进行 $dp[l][r-1][v-a_r]$ 次运算和 $1$ 次加法运算。以上两种情况中取最小值即为 $dp[l][r][v]$ 的值。在转移的过程中记录路径即可得到运算表达式。

已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度 （每层中自左至右输入），输入：一个正整数N结点数；然后输入N行，每行输入两个数字，中间用空格分开，代表节点及其对应的度。 输出：若该树有M个叶结点，则输出M行，每行是一条从根到叶子结点的路径，然后按照先序遍历的方式输出每一行。试写出构造此树的孩子-兄弟链表的c语言代码

以下是构造孩子-兄弟链表的C语言代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100005

typedef struct TreeNode {
    int data;
    struct TreeNode *firstChild;
    struct TreeNode *nextSibling;
} TreeNode;

TreeNode nodes[MAXN];
int degree[MAXN];

int buildTree(int n) {
    int root = -1;
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &nodes[i].data, &degree[i]);
        if (degree[i] == 0) continue;
        int firstChild = -1;
        for (int j = 0; j < degree[i]; ++j) {
            int child;
            scanf("%d", &child);
            if (firstChild == -1) {
                nodes[i].firstChild = &nodes[child];
                firstChild = child;
            } else {
                nodes[firstChild].nextSibling = &nodes[child];
                firstChild = child;
            }
        }
        if (root == -1) root = i;
    }
    return root;
}

void dfs(TreeNode *u, int path[], int depth) {
    path[depth] = u->data;
    if (u->firstChild == NULL) {
        for (int i = 0; i <= depth; ++i) {
            printf("%d ", path[i]);
        }
        printf("\n");
    }
    for (TreeNode *v = u->firstChild; v; v = v->nextSibling) {
        dfs(v, path, depth + 1);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int root = buildTree(n);
    int path[MAXN];
    dfs(&nodes[root], path, 0);
    return 0;
}

输入格式：

第一行一个整数 $n$，表示节点数。

接下来 $n$ 行，每行两个整数 $x$ 和 $k$，表示节点编号和该节点的度数，然后紧随其后 $k$ 个整数，表示该节点的 $k$ 个子节点编号。

输出格式：

若该树有 $m$ 个叶子结点，则输出 $m$ 行，每行是一条从根到叶子结点的路径，然后按照先序遍历的方式输出每一行。

样例输入：

7
0 4 1 2 3 4
1 2 5 6
2 0
3 1 7
4 0
5 0
6 0

样例输出：

0 1 5
0 1 6
0 2
0 3 7