Kruskal 1

添加一个超级源点，和每个点连一条边权为 A 的边。这样最小生成树必然能构成完整购买方案。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 501;
const int MAXM = MAXN * (MAXN - 1) / 2;
int n, m, A;
// e[i] 存第 i 条边 {边权,{起点,终点}}
pair<int, pair<int, int>> e[MAXM + 5];
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> n;
    m = 0;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++)
        {
            int w;
            cin >> w;
            if (w == 0)
                w = A;
            if (v > u)
                e[++m] = {w, {u, v}};
        }
    for (int i = 1; i <= n; i++)
        e[++m] = {A, {n + 1, i}};
    n++;

    sort(e + 1, e + m + 1);
    int ans = 0; // 选择的边的权值之和
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].second.first;
        int v = e[i].second.second;
        int w = e[i].first;
        int faU = findFa(u);
        int faV = findFa(v);
        if (faU == faV)
            continue;
        fa[faU] = faV;
        ans += w;
    }
    cout << ans;
    return 0;
}

Kruskal 2

边权超了 A 就停，每个连通块多买一个物品。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
const int MAXM = MAXN * (MAXN - 1) / 2;
int n, m, A;
// e[i] 存第 i 条边 {边权,{起点,终点}}
pair<int, pair<int, int>> e[MAXM + 5];
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> n;
    m = 0;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++)
        {
            int w;
            cin >> w;
            if (w == 0)
                w = A;
            if (v > u)
                e[++m] = {w, {u, v}};
        }

    sort(e + 1, e + m + 1);
    int num = n; // 连通块数量
    int ans = 0; // 选择的边的权值之和
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int u = e[i].second.first;
        int v = e[i].second.second;
        int w = e[i].first;
        if (w >= A)
            break;
        int faU = findFa(u);
        int faV = findFa(v);
        if (faU == faV)
            continue;
        num--;
        fa[faU] = faV;
        ans += w;
    }
    cout << ans + num * A;
    return 0;
}

Prim

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
const int MAXM = MAXN * (MAXN - 1) / 2;
int n, m, A;
int e[MAXN + 5][MAXN + 5];
int dis[MAXN + 5];  // 每个点到树的距离
bool vis[MAXN + 5]; // 每个点在不在树上
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> n;
    m = 0;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++)
        {
            cin >> e[u][v];
            if (e[u][v] == 0)
                e[u][v] = A;
        }

    // Prim
    for (int i = 1; i <= n; i++)
    {
        // 每个点选中都要 A 元
        // 相当于有一个超级根到每个点的距离都是 A
        dis[i] = A;
        vis[i] = false;
    }
    int ans = 0;
    for (int t = 1; t <= n; t++) // t 次选点入树
    {
        // 找离树最近的点
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!vis[i] && (u == -1 || dis[i] < dis[u]))
                u = i;
        // 这题显然有解，不用判无解也行
        if (u == -1)
            break;
        vis[u] = true;
        ans += dis[u];
        // 优化相邻点到树的距离
        for (int v = 1; v <= n; v++)
            dis[v] = min(dis[v], e[u][v]);
    }
    cout << ans;
    return 0;
}