POJ 3723 Conscription 最小生成树克鲁斯卡尔算法变形

浏览数：35 / 时间：2015年06月08日

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <cstring>

#define INF 100000000
using namespace std;
int n,m,r;
struct node{
	int x,y,w;
	bool operator < (const node &a)const{
		return w < a.w;
	}
};

int fa[20005];

int fun(int x){
	if(fa[x] == x) return x;
	else return fa[x] = fun(fa[x]);
}
int main(){
	int t;
	cin >> t;
	while(t--){
		priority_queue<node> que;
		scanf("%d%d%d",&n,&m,&r);
		for(int i = 0;i < r;i++){
			node  cc;
			scanf("%d%d%d",&cc.x,&cc.y,&cc.w);
			cc.y += 10000;
			que.push(cc);
		}
		
		long long int ans = 0;
		for(int i = 0;i < n;i++){
			fa[i] = i;
		}
		for(int i = 10000;i < m+10000;i++){
			fa[i] = i;
		}
		
		while(!que.empty()){
			node cc = que.top();
			que.pop();
			if(fun(cc.x) != fun(cc.y)){
				fa[fun(cc.x)] = fun(cc.y);
				ans += cc.w;
				
			}
		}	
		cout << (long long)(n+m)*10000- ans << endl;	
	} 
	return 0;
}

克鲁斯卡尔求最小生成树的思想是利用了从一个集合到另外一个集合的最小的边一定包含在这两个集合中点的最小生成树之中。同理这道题求得其实是这些点的最大生成树，同样可以用这种方法计算。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。