根据题意来分析， 要求出你选了几条路， 最小生成树是能解的， 那么就直接输出n - 1条路即可， 至于最大值则走一遍最小生成树求出即可
这里提供最小生成树的两种方法
1. 克鲁斯卡尔
克鲁斯卡尔算法还是比较好理解的思路也简单， 就是排序然后按顺序来遍历， 找一个就把他放到并查集中。
#include <iostream> #include <cstdio> #include <algorithm> #define MAXN 50005 using namespace std; int n, m, tot, fa[MAXN]; struct node { int x, y, z; }kls[MAXN]; bool cmp (node x, node y) { return x.z < y.z; } int find (int x) { if (fa[x] == x) return x; else return fa[x] = find (fa[x]); } int main () { scanf ("%d%d", &n, &m); for (int i = 1; i <= MAXN; i++) fa[i] = i; for (int i = 1; i <= m; i++) scanf ("%d%d%d", &kls[i].x, &kls[i].y, &kls[i].z); sort (kls + 1, kls + m + 1, cmp); int ans; for (int i = 1; i <= m; i++) { int xx = find (kls[i].x), yy = find (kls[i].y); if (xx != yy) { fa[xx] = yy; tot++; ans = kls[i].z; if (tot == n - 1) break; } } printf ("%d %d ", tot, ans); return 0; }
2.prim算法
有点类似于迪杰斯特拉。
#include <iostream> #include <cstdio> #include <cstring> #define MAXN 5005 using namespace std; int n, m, dis[MAXN], map[MAXN][MAXN]; bool vis[MAXN]; void prim () { dis[1] = 0; for (int i = 1; i <= n; i++) { int k = 0; for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] < dis[k]) k = j; vis[k] = 1; for (int j = 1; j <= n; j++) if (!vis[j] && dis[j] > map[k][j]) dis[j] = map[k][j]; } } int main () { memset (map, 0x7f7f7f, sizeof (map)); memset (dis, 0x7f7f7f, sizeof (dis)); scanf ("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int x, y, z; scanf ("%d%d%d", &x, &y, &z); if (map[x][y] > z) map[x][y] = map[y][x] = z; } prim(); int big = 0; for (int i = 1; i <= n; i++) if (dis[i] > big) big = dis[i]; printf ("%d %d ",n - 1, big); return 0; }