买礼物

洛谷-P1194-买礼物

实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;
struct edge {
    int u, v, w;
    bool operator < (const edge& o) const {
        return w > o.w; // 最大生成树
    }
};
int idx;
edge e[N * N];
int a, b;
int g[N][N];
int f[N];

int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}
bool query (int x, int y) {
    return find(x) == find(y);
}
int kruskal () {
    for (int i = 1; i <= b; ++ i) f[i] = i;
    sort(e + 1, e + idx + 1);
    int res = 0, cnt = 0;
    for (int i = 1; i <= idx; ++ i) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        if (query(u, v) == false) {
            merge(u, v);
            if (w > 0) res += w;
            if (++ cnt == b - 1) break;
        }
    }
    return res;
}

int main () {
    scanf("%d%d", &a, &b);
    for (int i = 1; i <= b; ++ i)
        for (int j = 1; j <= b; ++ j)
            scanf("%d", &g[i][j]);

    for (int i = 1; i <= b; ++ i)
        for (int j = i + 1; j <= b; ++ j)
            e[++ idx] = { i, j, (g[i][j] == 0 ? 0 : a - g[i][j]) };
    printf("%d", a * b - kruskal());
    return 0;
}