题目描述

在一张n个点的无向联通图中，求1号节点(Park)最大为k度时的最小生成树。(节点编号为字符串)

样例

样例输入

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

样例输出

Total miles driven: 183

算法1

(暴力枚举) $O(玄学)$

这是哪年的题了hhh...n<=20，大家想怎么做就怎么做吧...

时间复杂度分析：由您的代码决定。

C++ 代码

//自由发挥

算法2

(最小生成树) $O(n^2)$

总体思路：在这道题中，因为一号节点限定度数，可以考虑不断地连接一号节点到其他节点的边。

Step 1：删去从一号节点开始连向其他节点的边。则在图中会出现若干个连通块，如果联通块的数量 > k（限定的度数），则最后的图不连通。在每个连通块中跑一遍最小生成树。

Step 2：把每个连通块向一号节点连边。设连边的数量为t。如果 t < k，则可以考虑向一号节点加边。

Step 3： 那如何向一号节点加边？循环t – k次，枚举每条一号节点的出边， 如果该点不在最小生成树中，则找1号节点到该点的路径中最大边，将答案累加最大边的权值 – 该边的权值。

Step 4： 该过程可用树形dp实现，设dp[i].w表示1号节点到i号节点的路径上权值最大的边，dp[i].w = max(dp[fa[i]].w, i到fa[i]的边的权值。把答案累加最小1号节点到j号节点的权值 - dp[j].w的最小值 即可。

时间复杂度分析：O(nlog2n+m+kn)

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;

const int M = 55;
int n, m = 0, k, ans = 0;
int ee[M][M];
bool in[M][M];
// in表示in tree，即树边，同ee是邻接矩阵，in[i][j] = 1表示i到j有连边 
int tot = 0;
struct edge{
    int h, t, w;
}e[10010];
map <string, int> vis;

bool cmp(edge x, edge y) {
    return x.w < y.w;
}

int fa[M];
int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}

void Kruskal() {
    sort(e + 1, e + tot + 1, cmp);
    for (int i = 1; i <= m; ++ i) fa[i] = i;
    for (int i = 1; i <= tot; ++ i) {
        int x = e[i].h, y = e[i].t, z = e[i].w;
        int fx = get(x), fy = get(y);
        if (fx == 1 || fy == 1) continue;
        // 如果为1号节点则跳过 
        if (fx != fy) fa[fx] = fy, ans += z, in[x][y] = in[y][x] = 1;
    }
}

struct edges{
    int w, l, r;
}dp[M];
void dfs(int depth, int pre) {
    for (int i = 2; i <= m; ++ i) {
        if (i == pre || !in[depth][i]) continue;
        if (dp[i].w == -1) {
            if (dp[depth].w > ee[depth][i]) dp[i] = dp[depth];
            else dp[i].l = depth, dp[i].r = i, dp[i].w = ee[depth][i];
        }
        dfs(i, depth);
    }
}

int mintree[M], tminpoint[M];
// mintree[i]为1号节点到连通块i(并查集的编号)中的最短距离（即1号节点到连通块任何一点的边的最小权值），tminpoint[i]表示上述点的编号 
int num = 0, minpoint, point;
int main() {
    memset(ee, 0x3f, sizeof(ee));
    memset(mintree, 0x3f, sizeof(mintree));
    cin >> n;
    vis["Park"] = (++ m);
    for (int i = 1; i <= n; ++ i) {
        string x, y;
        int z;
        cin >> x >> y >> z;
        if (!vis[x]) vis[x] = (++ m);
        if (!vis[y]) vis[y] = (++ m);
        // 记录点数 
        int nx = vis[x], ny = vis[y];
        e[++ tot].h = nx, e[tot].t = ny, e[tot].w = z;
        ee[nx][ny] = ee[ny][nx] = min(ee[nx][ny], z);
    }
    //邻接表 + 邻接矩阵 
    cin >> k;
    Kruskal(); 
    for (int i = 2; i <= m; ++ i) 
        if (ee[1][i] < 0x3f3f3f3f) {
            int which = get(i);
            if (mintree[which] > ee[1][i]) {
                mintree[which] = ee[1][i];
                tminpoint[which] = i;
            }
        }
    // 查询1号节点到每个除1号节点连通块的最小距离即该边另一端的点的编号 
    for (int i = 1; i <= m; ++ i)
        if (mintree[i] < 0x3f3f3f3f) {
            ++ num;
            in[1][tminpoint[i]] = in[tminpoint[i]][1] = 1;
            ans += ee[1][tminpoint[i]];
        }   
    // 构建最小生成树，从1号节点向所有除1号节点的连通块连边，累计答案 
    for (int i = num + 1; i <= k; ++ i) {
        memset(dp, -1, sizeof(dp));
        dp[1].w = -0x3f3f3f3f;
        for (int j = 2; j <= m; ++ j)
            if (in[1][j]) dp[j].w = -0x3f3f3f3f;
        dfs(1, -1);
        // 树形dp求dp数组 
        minpoint = 0x3f3f3f3f;
        for (int j = 2; j <= m; ++ j) 
            if (minpoint > ee[1][j] - dp[j].w) minpoint = ee[1][j] - dp[j].w, point = j;
        if (minpoint >= 0) break;
        // 遍历求最小1号节点到j号节点的权值 - dp[j].w的最小值 
        in[1][point] = in[point][1] = 1;
        in[dp[point].l][dp[point].r] = in[dp[point].r][dp[point].l] = 0;
        // 处理善后 
        ans += minpoint;
        // 累计答案 
    }
    cout << "Total miles driven: " << ans << endl;
    return 0;
}