AcWing 347 Picnic Planning

题目描述

$blablabla$

样例解释

$blablabla$

思路概要

1.思之源：由于要求接上所有的小丑(即到达所有的节点)且要求总路径最短，我们可以凭借敏锐的嗅觉察觉到本题要求求出一棵最小生成树，但是公园的停车数有限(即$Park$的入度不得超过$s$)，对样例稍做分析，若假定$Park$为$1$号节点，不难想到这是一棵对$1$号节点的入度做出限制的最小生成树。
关键在于如何求解这棵最小生成树
2.思之扬：既然对1号节点的入度有限制，那我们就针对$1$号节点进行分析，通过稍加贪心，我们不妨先求出整张图的最小生成树，再以此为基础，
对整棵树稍加改变，枚举每一条与$1$号节点，找到代价最小的替代边，因为通过贪心，可得对最小生成树的改变越小，所求得的解越边权之和越小，越接近理想状态，那么我们就可以在超过限制的边缘疯狂试探，每一次改变都是当前状态下的改变程度最小的操作，并且当前入度一旦等于限制入度就停止操作，此时即为最优解。
3.实现思路：Prim算法求出最小生成树及其边权和，同时记录最小生成树中每条与$1$号节点相连的边，得到其入度，通过搜索最小生成树中所有与$1$号节点相连的边中代价最小的替代边，进行替换，并将$1$号节点的入度减一，将代价加入到最小生成树的边权和中，直至入度恰好为$s$，此时即为最优解，输出即可。
不附代码的题解不是好题解(doge)

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

using namespace std;

const int N = 35, M = 450;
const int INF = 0x3f3f3f3f;

int deg, n, ans, d[N], g[N][N];
int tr[N][N], cnt = 1, k, bridge[N];
map<string, int> mat;
bool v[N];

void Prim()//求解最小生成树
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    memset(v, 0, sizeof v);
    for(int i = 1; i < cnt; i ++)
    {
        int x = 0;
        for(int j = 1; j <= cnt; j ++)
            if(!v[j] && (x == 0 || d[x] > d[j])) x = j;

        v[x] = true;

        for(int j = 1; j <= cnt; j ++)
            if(!v[j] && d[j] > g[x][j])
            {
                d[j] = g[x][j];
                bridge[j] = x;
                //确定连接点，为下步求入度做准备
            }
    }

    memset(tr, 0x3f, sizeof tr);
    for(int i = 2; i <= cnt; i ++)
    {
        ans += d[i];
        if(bridge[i] == 1) deg ++;//求入度
        tr[i][bridge[i]] = tr[bridge[i]][i] = d[i];//记录最小生成树
    }
}

void dfs(int x)//确定最小生成树
{
    v[x] = true;
    for(int i = 1; i <= cnt; i ++)
        if(!v[i] && tr[x][i] != INF) dfs(i);
}

int find(int &x, int &y)//寻找最小代价边
{
    int minval = INF;
    for(int i = 2; i <= cnt; i ++) if(v[i])
        for(int j = 2; j <= cnt; j ++) if(!v[j])
            if(g[i][j] < minval){
                x = i, y = j;
                minval = g[i][j];
            }

    return minval;
}

void solve()
{
    int add = INF, mini, mins, mint;
    for(int i = 2; i <= cnt; i ++){
        if(tr[1][i] == INF) continue;
        memset(v, 0, sizeof v);
        v[1] = true;
        dfs(i);
        int x, y;
        int now = find(x, y);
        if(now < INF && now - tr[1][i] < add){
            mini = i, mins = x, mint = y;
            add = now - tr[1][i];
        }
    }

    ans += add;
    tr[1][mini] = tr[mini][1] = INF;
    tr[mins][mint] = tr[mint][mins] = g[mins][mint];
    //更新最小生成树
}

void inline read()
{
    memset(g, 0x3f, sizeof g);
    mat["Park"] = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int x, y, z;
        string a, b;
        cin >> a >> b;
        scanf("%d", &z);

        if(!mat.count(a)) mat[a] = ++ cnt;
        if(!mat.count(b)) mat[b] = ++ cnt;
        //map大法好
        x = mat[a], y = mat[b];
        g[x][y] = g[y][x] = min(g[y][x], z);
    }
    scanf("%d", &k);
}

int main()
{
    read();
    Prim();

    while(deg > k)
    {
        solve();
        deg --;
    }

    printf("Total miles driven: %d\n", ans);
    return 0;
}