本文主要是介绍poj 3723 kruscal，反边取最大生成树。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
需要征募女兵N人，男兵M人。
每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。
给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。
要求通过适当的招募顺序使得征募所有人的费用最小。
解析：
先设想无向图，在征募某个人a时，如果使用了a和b之间的关系，那么就连一条a到b的边。
假设这个图中存在圈，那么无论以什么顺序征募这个圈上的所有人，都会产生矛盾。
因此可以知道这个图是一片森林。
反之，如果给了一片森林，那么就可以使用对应的关系确定征募的顺序。
因此，把人看做顶点，关系看做边，这个问题就可以转化为求解无向图中的最大权森林问题。
最大权森林问题可以通过把所有边权取反（-号）之后用最小生成树去求解。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 20000 + 10;int fa[maxn];
int n, m, r;struct edge
{int fr, to;int w;
} e[maxn << 2];bool cmp(edge a, edge b)
{return a.w < b.w;
}int find(int x)
{if(x != fa[x])fa[x] = find(fa[x]);return fa[x];
}int kruscal()
{int res = 0;sort(e, e + r, cmp);for(int i = 0; i <= n + m; i++)fa[i] = i;for(int i = 0; i < r; i++){int t1 = find(e[i].fr);int t2 = find(e[i].to);if(t1 != t2){fa[t2] = t1;res += e[i].w;}}return res;
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALint ncase;scanf("%d", &ncase);while (ncase--){scanf("%d%d%d", &n, &m, &r);for (int i = 0; i < r; i++){scanf("%d%d%d", &e[i].fr, &e[i].to, &e[i].w);e[i].to = e[i].to + n;e[i].w = -e[i].w;}printf("%d\n", 10000 * (n + m) + kruscal());}return 0;
}
这篇关于poj 3723 kruscal，反边取最大生成树。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
