POJ 3723 Conscription 最小生成树

10000*总人数再减去图中的最大生成树即可，可以将权值取反求最小生成树

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int max_e = 5e4+5;
const int max_v = 2e5+5;
int T, n, m, r;
int fa[max_v];

struct edge
{
	int from, to, w;
}es[max_e];

void init()
{
	for(int i = 0; i < max_v; i++) fa[i] = i;
}

bool cmp(edge a, edge b)
{
	return a.w < b.w;
}
//并查集相关函数
int find(int x)
{
	if(fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}

void unite(int x, int y)
{
	int fx = find(x);
	int fy = find(y);
	fa[fx] = fy;
}

bool same(int x, int y)
{
	return find(x) == find(y);
}
//kruskal
int kruskal()
{
	init();
	sort(es, es+r, cmp);
	
	int res = 0;
	for(int i = 0; i < r; i++)
	{
		int u = es[i].from, v = es[i].to;
		if(!same(u, v))
		{
			unite(u, v);
			res += es[i].w;
		}
	} 
	return res;
}

int main()
{
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d %d", &n, &m, &r);
		for(int i = 0; i < r; i++)
		{
			scanf("%d %d %d", &es[i].from, &es[i].to, &es[i].w);
			es[i].to += n;  //男生的编号要加上女生的人数 
			es[i].w = -es[i].w;  //取相反数求最小生成树 
		}
		printf("%d\n", (n+m)*10000+kruskal());
	}
	return 0;
 }

POJ 3723 Conscription 最小生成树

原文：https://www.cnblogs.com/hucorz/p/14369003.html