程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3723 Conscription 最小生成樹 克魯斯卡爾算法變形

POJ 3723 Conscription 最小生成樹 克魯斯卡爾算法變形

編輯:C++入門知識

POJ 3723 Conscription 最小生成樹 克魯斯卡爾算法變形


 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 

#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 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;
}

克魯斯卡爾求最小生成樹的思想是利用了從一個集合到另外一個集合的最小的邊一定包含在這兩個集合中點的最小生成樹之中。同理這道題求得其實是這些點的最大生成樹,同樣可以用這種方法計算。

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved