大家好,又见面了,我是全栈君。
这一篇博客继续以一些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 <iostream> #include <cstdio> #include <algorithm> 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; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115547.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...