柚子快报激活码778899分享：树的专题整理(二)
这一篇博客继续以一些OJ上的题目为载体，对树专题进行整理整理一下。会陆续的更新。。。这是树的专题整理的第二篇博客，假设第一篇博客的地址在：http://blog.csdn.net/hjd_love_zzt/article/details/29401743例题：1、POJ 2485题目与分析：这道题抽象一下：“是求最小生成树的最大边”2)使用kruscal算法来解决/*
* POJ_2485_kruscal.cpp
*
* Created on: 2014年6月11日
* Author: Administrator
*/
#include
#include
#include
using namespace std;
const int maxn = 505;
const int maxm = maxn*maxn;
const int inf = 9999999;
int map[maxn][maxn];
int father[maxn];
int find(int x) {
if (x == father[x]) {
return x;
}
father[x] = find(father[x]);
return father[x];
}
void merge(int x, int y) {
int fx = find(x);
int fy = find(y);
if (fx != fy) {
father[fx] = fy;
}
}
struct Edge{
int begin;
int end;
int weight;
int selected;
}edge[maxm];
bool cmp(Edge a,Edge b){
if(a.weight != b.weight){
return a.weight < b.weight;
}
if(a.begin < b.begin){
return a.begin < b.begin;
}
return a.end < b.end;
}
int n,m;
int maxe;
int kruscal(){
int sum = 0;
int i;
for(i = 1 ; i <= n ; ++i){
father[i] = i;
}
sort(edge+1,edge+1+m,cmp);
int k = 0;
for(i = 1 ; i <= m ; ++i){
if( k == n-1){
break;
}
int x = find(edge[i].begin);
int y = find(edge[i].end);
if(x != y){
merge(x,y);
k++;
edge[i].selected = true;
sum += edge[i].weight;
maxe = edge[i].weight;//用来记录最下生成树中当前的最大边
}
}
return sum;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
m = 1;
int i;
int j;
for(i = 1 ; i <= n ; ++i){
for(j = 1 ; j <= n ; ++j){
scanf("%d",&map[i][j]);
}
}
for(i = 1 ; i <= n ; ++i){
for(j = i+1; j <= n ; ++j){
edge[m].begin = i;
edge[m].end = j;
edge[m].weight = map[i][j];
edge[m++].selected = false;
}
}
kruscal();
printf("%d\n",maxe);
}
return 0;
}
柚子快报激活码778899分享：树的专题整理(二)
推荐阅读
发表评论