include
include
include
include
include
include
include
include
include
include
include
include
include
#define IOS \
ios_base::sync_with_stdio(0); \
cin.tie(0);
define Mod 1000000007
define eps 1e -6
define ll long long
define INF 0x3f3f3f3f
define MEM (x, y) memset(x, y, sizeof(x))
define Maxn 1000000 + 10
using namespace std;
int N, M, R;
int x[Maxn], y[Maxn], d[Maxn];//男孩 女孩 关系度
struct edge
int u, v, cost;//u到v的距离为cost
bool cmp(const edge &e1, const edge &e2)//从小到大排序
return e1.cost < e2.cost;
edge es[Maxn];
int par[Maxn];
void init(int n)//初始化并查集
for (int i = 0; i
par[i] = i;
int findr(int x)//寻根
if (par[x] == x)
return x;
return par[x] = findr(par[x]);
void unite(int x, int y)//合并
x = findr(x);
y = findr(y);
if (x == y)
return;
par[x] = y;
bool same(int x, int y)//判断根是否相同
return findr(x) == findr(y);
int kruskal(int V, int E)//kruskal算法求最小生成树
sort(es, es + E, cmp);
init(V);
int res = 0;
for (int i = 0; i < E; i ++)
edge e = es[i];
if (!same(e.u, e.v))
unite(e.u, e.v);
res += e.cost;
return res;
int main()
int T;
scanf(“%d “, &T);
while (T –)//T组测试样例
scanf(“%d%d%d “, &N, &M, &R);//存数据
for (int i = 0; i < R; i ++)
scanf(“%d%d%d “, &x[i], &y[i], &d[i]);
int V, E;
V = N + M;//顶点个数
E = R;//边个数
for (int i = 0; i < E; i ++)//存入结构体
es[i] = (edge){
x[i], N + y[i], -d[i]};
printf(“%d \n “, 10000 * (N + M) + kruskal(V, E));
return 0;
Original: https://www.cnblogs.com/sky-stars/p/11587399.html
Author: Sky丨Star
Title: 【POJ 3723 】Conscription（最小生成树）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/611053/
转载文章受原作者版权保护。转载请注明原作者出处！