Poj 3723: Conscription

題目

分析

得先看透這題是在考 MST……

將人當成節點，關係當成邊，我們能節省的最大成本就是這個圖裡的 MST（實際上，是最大生成森林）

總共所須付的錢就是 10000 * (N + M) - reduce

AC Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long ll;

struct Edge {
    int u, v, cost;
    bool operator > (const Edge& e) const {
        return cost > e.cost;
    }
};

int N, M, R;
int V, E;
Edge edges[50000];

int parent[10000 * 2];
int height[10000 * 2];

void init() {
    for (int i = 0; i < V; i++) {
        parent[i] = i;
        height[i] = 0;
    }
}
int find(int a) {
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}
void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;

    if (height[a] < height[b])
        parent[a] = b;
    else {
        parent[b] = a;
        if (height[a] == height[b])
            height[a]++;
    }
}
bool same(int a, int b) {
    return find(a) == find(b);
}

ll solve() {
    // kruskal
    sort(edges, edges + E, greater<Edge>());
    init();

    ll cnt = 0;
    for (int i = 0; i < E; i++) {
        Edge& e = edges[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            cnt += e.cost;
        }
    }

    return cnt;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d %d %d", &N, &M, &R);

        for (int i = 0; i < R; i++) {
            int a, b, w;
            scanf("%d %d %d", &a, &b, &w);
            edges[i] = Edge{a, N + b, w};
        }

        V = N + M;
        E = R;

        ll reduce = solve();
        printf("%lld\n", 10000 * (N + M) - reduce);
    }

    return 0;
}

amoshyc/poj3723.md

Poj 3723: Conscription

題目

分析

AC Code