[POJ 3723]Conscription

danihao123 posted @ 2016年9月19日 21:59 in 题解 with tags POJ MST , 169 阅读
转载请注明出处:http://danihao123.is-programmer.com/

还是要注意读题(换言之,我英语很烂)……

这个题实际上要求求出一个最大生成森林。我们可以直接把边权造成负的,Kruskal一遍即可。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005;
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

// DJSet
int p[maxn*2],rank[maxn*2];
int find_set(int x){
	if(p[x]==x)
		return x;
	else
		return p[x]=find_set(p[x]);
}
void link_set(int x,int y){
	if(rank[x]>rank[y]){
		p[y]=x;
	}else{
		p[x]=y;
		if(rank[x]==rank[y])
			rank[y]++;
	}
}
inline void union_set(int x,int y){
	link_set(find_set(x),find_set(y));
}
inline bool is_same(int x,int y){
	return find_set(x)==find_set(y);
}
int n;
inline void init_set(){
	register int i;
	REP_B(i,n){
		p[i]=i;
	}
	CL_ARR(rank,0);
}

struct Edge{
	int u,v,d;
	bool operator <(const Edge& x) const{
		return d<x.d;
	}
};
int m;
Edge E[50005];
#define EDGE_ALL(i) E[i].u,E[i].v
int MST(){
	register int i,ans=0,cnt=0;
	init_set();
	sort(E+1,E+1+m);
	REP_B(i,m){
		if(!is_same(EDGE_ALL(i))){
			union_set(EDGE_ALL(i));
			ans+=E[i].d;
			cnt++;
			if(cnt==n-1)
				break;
		}
	}
	return ans;
}

int main(){
	int T,N,M;
	register int i,ans;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&N,&M,&m);
		n=N+M;
		ans=10000*n;
		for(i=1;i<=m;i++){
			scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d);
			E[i].u+=1;
			E[i].v+=1+N;
			E[i].d*=-1;
		}
		ans+=MST();
		printf("%d\n",ans);
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter