题目：野餐规划

网址：https://www.acwing.com/problem/content/349/

一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。

现在他们想要去公园玩耍，但是他们的经费非常紧缺。

他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。

为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。

由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。

公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须停在那里，不能再去接其他人。

现在请你想出一种方法，可以使得他们全都到达公园的情况下，所有汽车行驶的总路程最少。

输入格式

第一行包含整数$n$，表示人和人之间或人和公园之间的道路的总数量。

接下来$n$行，每行包含两个字符串$A$、$B$和一个整数$L$，用以描述人$A$和人$B$之前存在道路，路长为$L$，或者描述某人和公园之间存在道路，路长为$L$。

道路都是双向的，并且人数不超过$20$，表示人的名字的字符串长度不超过$10$，公园用$“Park”$表示。

再接下来一行，包含整数$s$，表示公园的最大停车数量。

你可以假设每个人的家都有一条通往公园的道路。

输出格式

输出$“Total miles driven: xxx”$，其中$xxx$表示所有汽车行驶的总路程。

输入样例：

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

此题其实是在说：给定一张图，让生成一颗最小生成树，要求结点$“Park”$连的边最多不超过$s$条。
令结点$“Park”$为$1$。

• 对于结点$1$，若断开所有的连边，产生$T$个联通分量，那么结点$1$最少也得连$T$条边；
• 最小生成树的子树也是最小生成树；

综上，我们可以进行以下过程：
1. 划分联通块；
2. 对每个联通块进行最小生成树运算；
3. 考虑结点$1$对每个联通块的边中权值最小的那一条边，连接并累和；
4. 进行$S - T$次迭代或直至不能继续更新，预处理每个节点到根节点的路径上的权值最大的边，对于每一条与结点$1$相连并且没被连接的边$(1, x)$，若结点$x$的最大权值边的权值大于该边，则替换。

实现细节挺多的。

代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#define pii pair <int, int>
using namespace std;
const int SIZE = 900 + 5;
struct node
{
    int u, v, w;
    inline bool operator <(const node& lhs)
    {
        return w < lhs.w;
    }
};
vector <node> e, path;
vector <int> G[SIZE], W[SIZE];
map <string, int> vertice;// 映射结点编号
map <pii, bool> chosen;//标记边是否被纳入 当前生成树 当中
bool vis[SIZE];
int n, S, T = 0, tot = 0, ans = 0, dfn[SIZE], fa[SIZE], dp[SIZE];
pii f[SIZE];
void init()
{
    e.clear(), vertice.clear();
    for(int i = 1; i <= 25; ++ i) fa[i] = i;
    chosen.clear(), vertice["Park"] = ++ tot;
    memset(vis, false, sizeof(vis));
    memset(dfn, -1, sizeof(dfn));
    return;
}
//并查集
int get(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
//染色 
void dfs(int u)
{
    dfn[u] = T;
    int v, w;
    for(int i = 0; i < G[u].size(); ++ i)
    {
        v = G[u][i], w = W[u][i];
        if(v == 1) continue;
        e.push_back((node)
        {
            u, v, w
        });
        if(dfn[v] == -1) dfs(v);
    }
    return;
}
//最小生成树系统
void Kruskal()
{
    sort(e.begin(), e.end());
    int x, y, v1, v2;
    for(int i = 0; i < e.size(); ++ i)
    {
        x = e[i].u, y = e[i].v, v1 = get(x), v2 = get(y);
        if(v1 == v2) continue;
        fa[v2] = v1;
        chosen[make_pair(x, y)] = chosen[make_pair(y, x)] = 1;
        ans += e[i].w;
    }
    return;
}
//预处理 简单路径 上权值最大的边
void bfs()
{
    memset(dp, 0, sizeof(dp));
    memset(vis, false, sizeof(vis));
    queue <int> Q;
    while(!Q.empty()) Q.pop();
    int u, v, w;
    Q.push(1);
    vis[1] = true;
    dp[1] = -1;
    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();
        for(int i = 0; i < G[u].size(); ++ i)
        {
            v = G[u][i], w = W[u][i];
            if(vis[v] || (!chosen[make_pair(u, v)] && !chosen[make_pair(v, u)])) continue;
            vis[v] = true;
            dp[v] = w;
            f[v] = make_pair(u, v);
            if(dp[v] < dp[u]) 
            {
                dp[v] = dp[u];
                f[v] = f[u];
            }
            Q.push(v);
        }
    }
    return;
}
int main()
{
    scanf("%d", &n);
    init();
    string A, B;
    int L;
    // input :
    for(int i = 0; i < n; ++ i)
    {
        cin >> A >> B >> L;
        if(vertice.find(A) == vertice.end()) vertice[A] = ++ tot;//这种形式很好
        if(vertice.find(B) == vertice.end()) vertice[B] = ++ tot;
        G[vertice[A]].push_back(vertice[B]), G[vertice[B]].push_back(vertice[A]);
        W[vertice[A]].push_back(L), W[vertice[B]].push_back(L);
    }
    //划分联通块 & 求出联通块内的最小生成树 
    for(int i = 2; i <= tot; ++ i)
    {
        e.clear();
        if(dfn[i] == -1)
        {
            ++ T;
            dfs(i), Kruskal();
        }
    }
    scanf("%d", &S);
    if(S < T)
    {
        printf("-1");
        return 0;
    }
    //对根节点的边进行挑选 
    for(int i = 1; i <= T; ++ i)
    {
        int val = 1 << 30, v;
        for(int j = 0; j < G[1].size(); ++ j)
        {
            if(dfn[G[1][j]] != i) continue;
            if(val > W[1][j]) val = W[1][j], v = G[1][j];
        }
        ans += val;
        chosen[make_pair(v, 1)] = chosen[make_pair(1, v)] = 1;
    }
    //进行 S - T 次循环 
    int u, w, x, tmp = 0, cnt = S - T;
    pii path;
    while(cnt)
    {
        bfs();
        for(int i = 0; i < G[1].size(); ++ i)
        {
            u = G[1][i], w = W[1][i];
            if(chosen[make_pair(1, u)]) continue;
            w = W[1][i];
            if(tmp < dp[u] - w) 
            {
                tmp = dp[u] - w;
                path = f[u];
                x = u;
            }
        }
        -- cnt;
        if(tmp <= 0) break;
        ans -= tmp;
        chosen[make_pair(path.first, path.second)] = chosen[make_pair(path.second, path.first)] = 0;
        chosen[make_pair(x, 1)] = chosen[make_pair(1, x)] = 1;
        tmp = 0;
    }
    printf("Total miles driven: %d\n", ans);
    return 0;
}