UVA1537 Picnic Planning

题目

UVA1537 Picnic Planning

算法标签: 最小生成树, $kruskal$重构树, 树形$dp$

思路

将$1$号点设置为终点, 然后执行重构树计算度数限制下的$MST$

重构树代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

const int N = 60, M = N * N, INF = 0x3f3f3f3f;

int n, k;

struct Edge {
   
    int u, v, w;

    bool operator<(const Edge &e) const {
   
        return w < e.w;
    }
} edges[N << 1];

int val[M], cnt, p[N];
map<string, int> mp;
int e_cnt;

void add(int u, int v, int w) {
   
    edges[e_cnt++] = {
   u, v, w};
}

int find(int x) {
   
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
   
    for (int i = 1; i <= cnt; ++i) p[i] = i;
    sort(edges, edges + e_cnt);

    int ans = 0;
    vector<int> vec;

    for (int i = 0; i < e_cnt; ++i) {
   
        auto &[u, v, w] = edges[i];
        int fa1 = find(u), fa2 = find(v);
        if (fa1 == fa2) continue;
        if (val[fa1] > val[fa2]) swap(fa1, fa2);
        p[fa2] = fa1;
        ans += w;
        //如果存在特殊边, 计算如果添加该边替换当前边的收益
        if (val[fa2] < INF >> 1) vec.push_back(val[fa2] - w);
    }

    int deg = 0;
    //必须添加的特殊边
    for (int i = 1; i <= cnt; ++i) {
   
        if (p[i] != i || i == 1) continue;
        deg++, ans += val[i];
    }

    sort(vec.begin(), vec.end());
    for (int i = 0; i < k - deg; ++i) ans += vec[i];

    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
   
        mp.clear();
        cnt = 0;
        e_cnt = 0;
        memset(val, 0x3f, sizeof val);
        mp["Park"] = ++cnt;
        cin >> n;

        for (int i = 0; i < n; ++i) {
   
            string a, b;
            int w;
            cin >> a >> b >> w;
            if (!mp[a]) mp[a] = ++cnt;
            if (!mp[b]) mp[b] = ++cnt;
            int u = mp[a], v = mp[b];

            //先将所有和1号点连接的点断开, 并且记录最小边权
            if (u == 1) val[v] = min(val[v], w);
            else if (v == 1) val[u] = min(val[u], w);
            else add(u, v, w);
        }

        cin >> k;

        int ans = kruskal();
        cout << "Total miles driven: " << ans << "\n";
    }
    return 0;
}