点击打开链接poj 1861
思路:最小生成树+并查集+kruskal
分析:
1 模板题,只要按照kruskal的思路即可。
2 题目要求输出的是最小生成树中最大边的最小值,以及多少条边和边的点
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 15010
int n , m;
int num[MAXN];
int father[MAXN];
int rank[MAXN];
struct Edge{
int x;
int y;
int value;
}e[MAXN];
bool cmp(Edge e1 , Edge e2){
return e1.value < e2.value;
}
void init_Set(){
for(int i = 0 ; i <= n ; i++){
father[i] = i;
rank[i] = 0;
}
}
int find_Set(int x){
if(father[x] != 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;
}
}
void kruskal(){
init_Set();
sort(e , e+m , cmp);
int cnt = 0;
for(int i = 0 ; i < m ;i++){
int root_x = find_Set(e[i].x);
int root_y = find_Set(e[i].y);
if(root_x != root_y){
union_Set(root_x , root_y);
num[cnt++] = i;
}
}
printf("%d\n%d\n" , e[num[cnt-1]].value , cnt);
for(int i = 0 ; i < cnt ; i++)
printf("%d %d\n" , e[num[i]].x , e[num[i]].y);
}
int main(){
while(scanf("%d%d" , &n , &m) != EOF){
for(int i = 0 ; i < m ; i++)
scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
kruskal();
}
return 0;
}
分享到:
相关推荐
利用并查集判断环路,以及快速排序计算最小生成树
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ2531-Network Saboteur 解题报告+AC代码
poj 1459 Power Network.md
北大POJ1459-Power Network 解题报告+AC代码
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分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案