题面

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

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

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

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

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

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

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

输入格式

第一行包含整数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

题解

解法一(状压dp)

最小生成树的子树还是最小生成树

先把题目中的s限制去掉, 就是求G = (V, E)的最小生成树

所以我们就是把G的最小生成树链接根(Park)的一些边去掉, 断出来一些子最小生成树

然后通过一些和这些子最小生成树相连的边(另一端必须连在Park上), 将断出来的子树重新练回Park

求得就是最小花费

思路清楚了, 就好写了

d[i][0] 表示第i棵子树链接Park的最小权值

d[i]j 表示第i棵子树和第j棵链接的边的最小权值

最多有20棵子树, 直接状压选择哪些子树还连在Park, 然后再选择断出来的子树连回去的最小边相加

最后取最小值就行了

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;

const int maxn = 22;

struct rec { int x, y, z; } e[2000];

bool operator<(rec& a, rec& b) { return a.z < b.z; }

int n, s, fa[maxn], ans, v[maxn], res;
int b[maxn], cnt, d[maxn][maxn];
unordered_map<string, int> mp;

int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); }

void dfs(int cur, int k, int m, int p)
{
    if (cur >= res || (cnt - p + 1) < k) return;
    if (m == cnt) { res = cur; return; }

    if (k)
    {
        rep(i, p, cnt)
            if (!v[i])
            {
                v[i] = 1;
                dfs(cur + d[i][0], k - 1, m + 1, i + 1);
                v[i] = 0;
            }
    }
    else
        rep(i, 1, cnt)
        if (!v[i])
        {
            v[i] = 1;
            int mi = 2e9;
            rep(j, 1, cnt) if (v[j]) mi = min(mi, d[i][j]);
            dfs(cur + mi, 0, m + 1, 0);
            v[i] = 0;
        }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n; mp["Park"] = 0;

    rep(i, 1, n)
    {
        string a, b; int c;
        cin >> a >> b >> c;
        if (!mp.count(a)) mp[a] = mp.size();
        if (!mp.count(b)) mp[b] = mp.size();
        e[i] = { mp[a], mp[b], c };;
    } cin >> s;

    rep(i, 1, 21) fa[i] = i;
    memset(d, 0x3f, sizeof d);
    sort(e + 1, e + n + 1);

    rep(i, 1, n)
    {
        int x = get(e[i].x), y = get(e[i].y);
        if (y == 0) y = x, x = 0;
        if (x == y || (x == 0 && b[y])) continue;
        if (x == 0) { d[++cnt][0] = e[i].z; b[y] = cnt; res += e[i].z; }
        else if (b[x] && b[y])
        {
            d[b[y]][b[x]] = min(d[b[y]][b[x]], e[i].z);
            d[b[x]][b[y]] = d[b[y]][b[x]];
        }
        else if (b[x]) fa[y] = x, ans += e[i].z;
        else if (b[y]) fa[x] = y, ans += e[i].z;
        else fa[y] = x, ans += e[i].z;
    }

    if (cnt > s) { res = 1e9; dfs(0, s, 0, 1); }
    cout << "Total miles driven: " << ans + res;
    return 0;
}

解法二 优先队列

已经被@soul_of_sky 佬 hack了，需要在优先队列出边的时候，对点打标记，去处理@soul_of_sky 佬所说的问题，暂时考虑并查集（感觉这么些还有问题

要用优先队列就不用在被20人限制取用状压做,

限制变成了有多少条边的限制

先把s的限制扔掉, 那就是普通的最小生成树, 对边排序就好了

有了s的限制怎么办呢?

无非就是选选择没选过的边, 将和 “Park” 相连的两个子孩子合并, 就行

至于花费, 在维护并查集的时候带权d[i], 表示i集合到 “Park” 的最短距离

然后就是向优先队列加边(边不连接”Park) 贡献为 e[i].cost - max(d[x], d[y])

时间复杂度

菜鸡自推，如有错误，请指正

设共有n个点, m条边不连接park(这题不考虑重边), k个停车场,

一个点的修改，会影响与其他 $n - 1$ 个点相连的边，所以最坏修改优先队列里边的权值次数为 $sum = \sum_{i=1}^{n-1}i$, 也就是 $n^2$, 然后最多拆除和park相连的 $n - 1$ 条边($k = 1$)，也就是从优先队列中取出 $n - 1$ 次值, 复杂度为 $nlogm$; 刚开始初始化有限队列的次数则是 $m$

使用$pbds$中的$thin_heap_tag$, 其插入节点复杂度为$O(1)$, 修改节点复杂度均摊为$\Theta(1)$,出队均摊为$\Theta(logn)$

故总复杂度为 $\Theta(nlogn + mlogm + m + n^2 + nlogm)=\Theta(mlogm + n^2)$

而$m <= \sum_{i=1}^{n-1}i$, 故$\Theta(n^2(2logn + 1))$

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;

const int N = 21;

struct node { int x, y, c; } e[200000];

int n, f[N], d[N], ans, s, m;
string t;
unordered_map<string, int> st;

// id连接集合Sx和Sy的边的索引, 断开(park, x) 使得Sx合并Sy
struct node2 {
    int id, x, y;
    node2(int Id = 0, int X = 0, int Y = 0): id(Id), x(X), y(Y) {}
    bool operator()(const node2& a, const node2& b) {
        return e[a.id].c - d[a.x] > e[b.id].c - d[b.x];
    }
};

int get(string& str) {
    if (st.count(str)) return st[str];
    return st[str] = st.size(), int(st.size() - 1);
}

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

void add(int id, __gnu_pbds ::priority_queue<node2, node2, thin_heap_tag> &q) {
    int x = find(e[id].x), y = find(e[id].y);
    if (x == y) return;
    if (d[x] > d[y]) q.push({id, x, y});
    else q.push({id, y, x});
}

int main() {
    t = "Park"; get(t); cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> t; e[i].x = get(t); cin >> t >> e[i].c; e[i].y = get(t);
    } sort(e, e + n, [](node& a, node& b) { return a.c < b.c; });
    cin >> s; m = int(st.size() - 1);
    for (int i = 1; i <= m; ++i) f[i] = i, d[i] = 1e9;
    vector<int> a;
    for (int i = 0; i < n; ++i) {
        int x = find(e[i].x), y = find(e[i].y);
        if (x == y) continue;
        if (x > y) swap(x, y);
        if (!x) { d[y] = min(d[y], e[i].c); continue; }
        if (max(d[x], d[y]) == 1e9) f[y] = x, ans += e[i].c, d[x] = min(d[x], d[y]), --m;
        else a.emplace_back(i);
    }
    for (int i = 1; i < st.size(); ++i) if (i == f[i]) ans += d[i];

    __gnu_pbds ::priority_queue<node2, node2, thin_heap_tag> q;
    for (auto& i : a) add(i, q);
    while (m > s) {
        auto p = q.top();
        int x = find(p.x), y = find(p.y);
        if (x == y) continue;
        if (x != p.x) {
            if (d[x] > d[y]) q.modify(q.begin(), {p.id, x, y});
            else q.modify(q.begin(), {p.id, y, x});
        } else {
            ans += e[p.id].c - d[p.x];
            --m; f[x] = y; q.pop();
        }
    }
    cout << "Total miles driven: " << ans;
    return 0;
}