Zerojudge e509：Conscription

Zerojudge e509：Conscription

題目大意：有 $n$ 位女孩和 $m$ 位男孩，想要應召他們，每人 $10000$ 元，但有些人有戀愛關係，可以扣除 $d$ 元，只要關係不相互影響 (假設 $a,b,c,d$ 有戀愛關係，$ab$ 可扣除，$bc$ 可扣除，$cd$ 可扣除，但 $da$ 就不可扣除)，問最少要花幾元。

解法：求最大生成樹(最小生成樹的變種，且不須每個點都連通，可用Kruskal演算法)，將男孩的編號都加上 $n$，由大到小排序，再依序加入邊，要判斷兩點有沒有連在一起，可用並查集，最後再用 $10000\times (n+m)-$權重總和就是答案。

$\text{Code：}$ 男孩($b$)和女孩($g$)弄反了，不過都沒差

#pragma GCC optimize("O3")
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
struct edge {
    int b, g, c;
    void init() {
        cin >> b >> g >> c;
    }
    bool operator< (const edge &that) const {
        return this->c > that.c;
    }
} e[50005];
int to[20005];
int find_to (int x) {
    if (to[x] == -1)
        return x;
    return to[x] = find_to (to[x]);
}
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    int t;
    cin >> t;
    while (t--) {
        int n, m, r, sum = 0;
        cin >> n >> m >> r;
        memset (to, -1, sizeof (to));
        for (int i = 0; i < r; i++)
            cin >> e[i].b >> e[i].g >> e[i].c, e[i].g += n;
        sort (e, e + r);
        for (int i = 0; i < r; i++) {
            int fb = find_to (e[i].b), fg = find_to (e[i].g);
            if (fb == fg)
                continue;
            sum += e[i].c;
            to[fg] = fb;
        }
        cout << 10000 * (n + m) - sum << '\n';
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！