最小生成树--模板

板子：

int V, E;
int p[MAXN];
int r[MAXN];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        p[i] = i, r[i] = 0;
    }
}

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }

bool same(int x, int y) { return find(x) == find(y); }

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (r[x] < r[y]) {
        p[x] = y;
    } else {
        p[y] = x;
        if (r[x] == r[y]) r[x]++;
    }
}

struct Edge {
    int u, v, cost;
} edge[MAXM];
bool cmp(const Edge& e1, const Edge& e2) { return e1.cost < e2.cost; }
int Kruskal() {
    sort(edge + 1, edge + R + 1, cmp);
    init(V);
    int res = 0;
    for (int i = 1; i <= E; i++) {
        Edge e = edge[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

---

题意：N个城堡，M个桥，每个桥的权值都不一样，题目要求能使城堡彼此联通的所有桥集合里面权值最小的那种，由此可以判断这是一道求最小生成树的题。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn = 2000 + 5, maxm = 2e5 + 5;
struct edge {
    int u, v, value;
}myedge[maxm];
int p[maxn], n, m;

bool cmp(const edge&p1,const edge&p2) {
    return p1.value < p2.value;
}

int find(int x) {
    return (p[x] == x) ? x : (p[x] = find(p[x]));
}

int main() {
    scanf("%d%d", &n, &m);
    int a, b, id, k = 0;
    ll w;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%lld%d", &a, &b, &w, &id);
        if (id == 1) {
            myedge[k].u = a;
            myedge[k].v = b;
            myedge[k].value = w;
            k++;
        }
    }
    if (k != 0) {
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        sort(myedge, myedge + k, cmp);
        int x, y, counter = 0;
        ll value, sum = 0;
        for (int i = 0; i < k; i++) {
            value = myedge[i].value;
            x = find(myedge[i].u);
            y = find(myedge[i].v);
            if (x != y) {
                sum += value;
                p[y] = x;
                counter++;
                if (counter >= n - 1) break;
            }
        }
        printf("yes
%lld
", sum);
    }
    else printf("no");
    return 0;
}

---

POJ3723

题意：有 N 个男人 M 个女人，给出若干男女之间的 1~9999 之间的亲密度关系，征募某个人的费用是 10000 -（已经征募到的人中和自己的亲密度的最大值）。要求通过适当的征募顺序使得所有人的所需费用最小

解法：把人与人看做点，则这个问题就转换为无向图中的最大权森林问题。将最小生成树中的边权去反即可用最小生成树的算法求解。

int N, M, R;
int p[MAXN];
int r[MAXN];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        p[i] = i, r[i] = 0;
    }
}

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }

bool same(int x, int y) { return find(x) == find(y); }

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (r[x] < r[y]) {
        p[x] = y;
    } else {
        p[y] = x;
        if (r[x] == r[y]) r[x]++;
    }
}

struct Edge {
    int u, v, cost;
} edge[MAXM];

bool cmp(const Edge& e1, const Edge& e2) { return e1.cost < e2.cost; }

LL Kruskal() {
    sort(edge + 1, edge + R + 1, cmp);
    init(N + M);
    LL res = 0;
    for (int i = 1; i <= R; i++) {
        Edge e = edge[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main() {
    // freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &N, &M, &R);
        REP(i, 1, R) {
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
            edge[i].u++, edge[i].v++;
            edge[i].cost = 0 - edge[i].cost;
            edge[i].v = edge[i].v + N;
        }
        printf("%lld
", 10000 * 1ll * (N + M) + Kruskal());
    }
    return 0;
}