地址 https://www.papamelon.com/problem/245
需要征募女兵 N 人,男兵 M 人。
每征募一个人需要花费 10000 人民币。如果两个人之间有某种关系，则可以少花钱。
例如，一男一女之间的关系值为 d，其中一人已经被征募，当我们再征募第二个人时，花费为 10000−d 元。
多人之间可以形成环状关系，来看一个例子：
A 和 B 有关系，可减免 100 元
B 和 C 有关系，可减免 200 元
C 和 A 有关系，可减免 300 元
招募 A 花费 10000 元
招募 B，因为有 A，减免 100 元，花费 10000−100 元
招募 C，因为有 B，减免
200 元，花费 10000−200 元
尽管 C 和 A 之间有关系，但 A,B,C 都招进来了，无法再减免，总花费是
30000−300 元
以上只是一种招人方案，并不一定是最省钱的
现在给出所有的关系信息，让我们征募到
N 女 M 男，求最小花费。
输入
第一行整数 T(1≤T≤10)，表示有多少组测试数据
每组测试数据最开始先是一个空行，再接着以下的部分：
第一行有 3 个整数
N 和 M 和 R
接下来的 R 行，每行均表示一条人际关系，三个整数
x,y,d, 表示女兵 x 和男兵 y 的关系值为 d
1≤N,M≤10000
1≤R≤50000
0<d<10000
0≤x<N
0≤y<M
输出T 行，每行一个整数，表示该组测试数据中所需的最小费用
样例 1
输入
2
5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781
5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133
输出
71071
54223
解答
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
const int N = 200010, M = 500010;
struct Edge {
int a, b, w;
bool operator<(const Edge& e) {
return w > e.w;
}
}edges[M];
int f[N];
int t, m, n, r;
int find(int x) {
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
int kruskal() {
sort(edges, edges + r);
cout <<edges[0].w <<" "<<edges[1].w<<endl;
for (int i = 0; i <= m + n; i++) f[i] = i;
int res = 0;
for (int i = 0; i < r; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a); b = find(b);
if (a != b) {
f[a] = b;
res += w;
}
}
return res;
}
int main() {
cin >> t;
while (t--) {
cin >> n >> m >> r;
memset(edges, 0, sizeof edges);
for (int i = 0; i < r; i++) {
int a, b, w; cin >> a >> b >> w;
edges[i].a = a; edges[i].b = b+n; edges[i].w = w;
}
int t = kruskal();
cout << 10000 * (m + n) - t << endl;
}
return 0;
}