点击打开链接poj 3723
思路:kruskal + 最小生成树
分析:
1 首先我们应该区分开男孩和女孩,只要将男孩的编号加上女孩的个数n,这样就可以做到男孩和女孩的编号是不同的。
2 题目中说了如果两个人有关系,并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题,那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面,每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最小生成树相加,然后在加上s*10000(没有关系的时候选择一个人要10000),即为最后的答案。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 50010
int t , n , m , r;
int father[MAXN];
int rank[MAXN];
struct Edge{
int x;
int y;
int value;
}e[MAXN];
void init_Set(){
memset(rank , 0 , sizeof(rank));
for(int i = 0 ; i <= n+m ; i++)
father[i] = i;
}
int find_Set(int x){
if(x != father[x])
father[x] = find_Set(father[x]);
return father[x];
}
void union_Set(int x , int y){
if(rank[x] > rank[y])
father[y] = x;
else{
if(rank[x] == rank[y])
rank[y]++;
father[x] = y;
}
}
bool cmp(Edge e1 , Edge e2){
return e1.value < e2.value;
}
void kruskal(){
int ans = 0;
sort(e , e+r , cmp);
/*求出s个集合的最小生成树的和*/
for(int i = 0 ; i < r ; i++){
int root_x = find_Set(e[i].x);
int root_y = find_Set(e[i].y);
if(root_x != root_y){
ans += e[i].value;
union_Set(root_x , root_y);
}
}
/*求有几个集合*/
int cnt = 0;
int vis[MAXN];
memset(vis , 0 , sizeof(vis));
for(int i = 0 ; i < n+m ; i++){
int tmp = find_Set(i);
if(!vis[tmp]){
cnt++;
vis[tmp] = 1;
}
}
printf("%d\n" , ans+10000*cnt);
}
int main(){
int a , b , v;
scanf("%d" , &t);
while(t--){
scanf("%d%d%d" , &n , &m , &r);
init_Set();
for(int i = 0 ; i < r ; i++){
scanf("%d%d%d" , &a , &b , &v);
e[i].x = a;
e[i].y = b+n;
e[i].value = 10000-v;/*边的权值*/
}
kruskal();
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
北大POJ2002-Squares 解题报告+AC代码
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
POJ1048,加强版的约瑟夫问题 难度中等
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
Poj中一些题目的源代码,里面共有二十多道题目,OI
POJ2968代码有用,欢迎下载,POJ代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码