题目分析

本题要求找到一种方案，使得所有兄弟前往公园时，车辆行驶的总英里数最小。核心难点在于如何在满足停车场容量限制的情况下，合理规划兄弟之间的拼车路径，以达到总行驶里程最小化的目标。

代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

const int maxn = 111 + 5;
const int maxe = 15000 + 5;
const int INF = 460002326;
#include <map>
map<string, int> mp;
map<string, int>::iterator it;
int car, n, cost[maxn][maxn], sum, father[maxn];
int best[maxn];
bool vis[maxn];
bool edge[maxn][maxn];
bool use[maxn];

// 将一个连通块中各个点标记其father
void dfs(int root) {
    for (int i = 1; i < n; i++) {
        if (vis[i] && edge[root][i]) {
            father[i] = root;
            vis[i] = false;
            dfs(i);
        }
    }
}

// Prim算法构建最小生成树
void prim(int s) {
    int Min_i, Min, dis[maxn], num[maxn];
    memset(vis, false, sizeof(vis));
    for (int i = 0; i < n; i++) {
        dis[i] = cost[i][s];
        num[i] = s;
    }
    dis[s] = 0;
    vis[s] = use[s] = true;
    while (true) {
        Min = INF, Min_i = -1;
        for (int i = 0; i < n; i++) {
            if (!use[i] &&!vis[i] && (Min_i == -1 || Min > dis[i])) {
                Min_i = i;
                Min = dis[i];
            }
        }
        if (Min == INF)    break;
        sum += Min;
        vis[Min_i] = true;
        use[Min_i] = true;
        edge[Min_i][num[Min_i]] = edge[num[Min_i]][Min_i] = true;
        for (int i = 0; i < n; i++) {
            if (!use[i] &&!vis[i] && dis[i] > cost[i][Min_i]) {
                num[i] = Min_i;
                dis[i] = cost[i][Min_i];
            }
        }
    }
    Min = INF;
    int root = -1;
    for (int i = 0; i < n; i++) {
        if (vis[i] && cost[0][i] < Min && i!= 0) {
            Min = cost[0][i];
            root = i;
        }
    }
    vis[root] = false;
    dfs(root);
    father[root] = 0;
    sum += Min;
}

// 更新其中各个点到park路径上边权值最大的点
int Best(int j) {
    if (father[j] == 0)
        return best[j] = -1;
    if (best[j]!= -1) return best[j];
    int tmp = Best(father[j]);
    if (tmp!= -1) {
        if (cost[tmp][father[tmp]] > cost[father[j]][j])
            best[j] = tmp;
        else best[j] = j;
    }
    else best[j] = j;
    return best[j];
}

// 解决问题的主函数
void solve() {
    int mst = 0;
    memset(father, -1, sizeof(father));
    memset(use, 0, sizeof(use));
    memset(edge, false, sizeof(edge));
    use[0] = true;
    for (int i = 0; i < n; i++) {
        if (!use[i]) {
            prim(i);
            mst++;
        }
    }
    for (int i = mst + 1; i < n && i <= car; i++) {
        memset(best, -1, sizeof(best));
        for (int j = 0; j < n; j++) {
            if (j!= 0 && best[j] == -1 && father[j]!= 0)
                Best(j);
        }
        int minadd = INF;
        int ax, bx, change;
        for (int j = 0; j < n; j++) {
            if (cost[0][j]!= INF && father[j]!= 0) {
                ax = best[j];
                bx = father[ax];
                if (minadd > cost[0][j] - cost[ax][bx]) {
                    minadd = cost[0][j] - cost[ax][bx];
                    change = j;
                }
            }
        }
        if (minadd >= 0)
            break;
        sum += minadd;
        ax = best[change];
        bx = father[ax];
        cost[ax][bx] = cost[bx][ax] = INF;
        father[change] = 0;
        cost[0][change] = cost[change][0] = INF;
    }
}

int main() {
    int t;
    // freopen("in.txt","r",stdin);
    cin >> t;
    mp.clear();
    string s1, s2;
    int val;
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxn; j++)
            cost[i][j] = INF;
    n = 1, sum = 0;
    mp["Park"] = 0;
    for (int i = 0; i < t; i++) {
        cin >> s1 >> s2 >> val;
        it = mp.find(s1);
        if (it == mp.end())
            mp[s1] = n++;
        it = mp.find(s2);
        if (it == mp.end())
            mp[s2] = n++;
        if (cost[mp[s1]][mp[s2]] > val)
            cost[mp[s1]][mp[s2]] = cost[mp[s2]][mp[s1]] = val;
    }
    cin >> car;
    solve();
    cout << "Total miles driven: " << sum << endl;
    return 0;
}

复杂度分析

1. 时间复杂度
   • 图的构建：每次输入边的时间复杂度为$O(1)$，共$t$条边，所以构建图的时间复杂度为$O(t)$ 。
   • Prim算法：每次Prim算法的时间复杂度为$O(n^2)$，最坏情况下需要执行$n$次（每个点都作为起点），所以Prim算法部分的时间复杂度为$O(n^3)$。
   • 调整最小生成树：每次寻找可调整的节点并更新的时间复杂度为$O(n)$，最多执行$n - 1$次，所以这部分时间复杂度为$O(n^2)$。
   • 总体时间复杂度：由于$t$与$n$相关，且在实际情况中$n$相对较小（题目中节点数有限制），整体时间复杂度主要由Prim算法主导，为$O(n^3)$ 。