洛谷题单指南-最小生成树-P1194 买礼物

原题链接：https://www.luogu.com.cn/problem/P1194

题意解读：每个物品都有价格a，如果手上有物品i，且i->j有非0权值，那么买只用花该权值也可以买j，求用最少的钱买到所有物品。

解题思路：

方法一、直接思考

考虑如何买每一个物品：

设待买的物品为t

如果t与已经买的物品之间有小于a的权值d，那么只用花费d就可以买到t，否则要花费a

对于已经购买的物品，形成一个集合，如何确定下一个要买的物品？

根据贪心原则，显然下一个物品与集合中物品的权值越小越好，这不就是prim算法吗？

设物品是节点，物品与物品之间权值不为0则建边，为0则不建边或者用邻接矩阵表示就是无穷大。

然后从1开始跑一遍prim，需要注意的是：

1、1号物品必选，dist[1]可以初始化为a

2、将物品选入集合是，价格有两种选择，应该取min(边权值，a)

3、为了避免出现有些点无法连通，在寻找不在集合中距离集合最近的点时判断要用dist[j] <= dist[t]，这样才能选出dist[x]=INF的点

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 505, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool vis[N];
int a, b, ans;

int main()
{
    cin >> a >> b;
    for(int i = 1; i <= b; i++)
        for(int j = 1; j <= b; j++)
        {
            int w;
            cin >> w;
            if(w == 0) g[i][j] = INF; //注意0表示不会优惠，因此价格要设置无穷大，便于比较
            else g[i][j] = w;
        }

    memset(dist, 0x3f, sizeof(dist));
    dist[1] = a; //1号点必选,花费肯定是a，不要设置为0，后面累加花费是会取min
    for(int i = 1; i <= b; i++)
    {
        int t = 0;
        for(int j = 1; j <= b; j++) //找到集合外距离集合最近的点t
            if(!vis[j] && (t == 0 || dist[j] <= dist[t])) //dist[j] <= dist[t]如果集合外的点与集合中的点都不连通的时候，也可以找到一个点
                t = j;
        vis[t] = true;
        ans += min(dist[t], a); //选取t的时候，根据边长和a的大小去较小值
        //用t更新相邻节点的dist
        for(int j = 1; j <= b; j++) 
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    cout << ans;

    return 0;
}

方法二：虚拟礼物

每个礼物要么直接买，要么通过买其他相邻的礼物顺便买，且第一个礼物必须直接买。

可以假设一个虚拟礼物，编号为0，对于其他所有礼物都有K[0][i]=K[i][0]=a，那么在0到其他节点都建立一条长度为a的边。

这样，所有礼物都可以表示成0~b的点，购买所有礼物就是要使得0~b的点都连通。

在整个图中跑一次最小生成树，即可得到购买所有礼物的最小花费。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 505, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
bool vis[N];
int a, b, ans;

int main()
{
    cin >> a >> b;
    for(int i = 1; i <= b; i++)
    {
        g[0][i] = g[i][0] = a; //虚拟0点
        for(int j = 1; j <= b; j++)
        {
            int w;
            cin >> w;
            if(w == 0) g[i][j] = INF; //注意0表示不会优惠，因此价格要设置无穷大，便于比较
            else g[i][j] = w;
        }
    }

    memset(dist, 0x3f, sizeof(dist));
    //正常跑一遍prim
    dist[0] = 0; 
    for(int i = 0; i <= b; i++)
    {
        int t = -1; //从0开始选，初始设为-1
        for(int j = 0; j <= b; j++) //找到集合外距离集合最近的点t
            if(!vis[j] && (t == -1 || dist[j] < dist[t])) 
                t = j;
        vis[t] = true;
        ans += dist[t];
        //用t更新相邻节点的dist
        for(int j = 0; j <= b; j++) 
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    cout << ans;

    return 0;
}