POJ 2485 Highways(最小生成树)
http://poj.org/problem?id=2485
题意:
给你一个N个节点的无向图,以及它的距离矩阵.现在要你求该图的最小生成树,并输出该树中最长边的长度.
分析:
直接构建最小生成树,并输出最后一条加入生成树的边即可.(我这里用的kruskal算法)
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500+10;
const int maxm=500*500+10;
struct Edge
{
int u,v,dist;
Edge(){}
Edge(int u,int v,int d):u(u),v(v),dist(d){}
bool operator<(const Edge &rhs)const
{
return dist<rhs.dist;
}
};
struct Kruskal
{
int n,m;
Edge edges[maxm];
int fa[maxn];
int findset(int x){ return fa[x]==-1? x: fa[x]=findset(fa[x]); }
void init(int n)
{
this->n=n;
m=0;
memset(fa,-1,sizeof(fa));
}
void AddEdge(int u,int v,int dist)
{
edges[m++]=Edge(u,v,dist);
}
int kruskal()//范围生成树中最长边的值
{
int sum=0;
int cnt=0;
sort(edges,edges+m);
for(int i=0;i<m;i++)
{
int u=edges[i].u, v=edges[i].v;
if(findset(u) != findset(v))
{
sum += edges[i].dist;
fa[findset(u)] = findset(v);
if(++cnt>=n-1) return edges[i].dist;
}
}
return -1;
}
}KK;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
KK.init(n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
int dist;
scanf("%d",&dist);
if(i<j)
{
KK.AddEdge(i,j,dist);
}
}
printf("%d\n",KK.kruskal());
}
return 0;
}
分享到:
相关推荐
poj 2485 Highways 测试数据 解题报告:http://blog.csdn.net/qq7366020/article/details/8615293
北大POJ2485-Highways【Prim】 解题报告+AC代码
Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be ...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
北大2485的简单题目。用了最小生成树,在VS上编译,并成功提交。
NULL 博文链接:https://200830740306.iteye.com/blog/603493
NULL 博文链接:https://128kj.iteye.com/blog/1704752
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
度限制最小生成树代码 摘自POJ1639代码
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
poj2516代码最小费用最大流
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
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题解 个人写法 线段树每个人都不一样
4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流...
利用并查集判断环路,以及快速排序计算最小生成树
poj经典数据结构题目解题报告,包括经典的数据结构题目10多道,可以作为学习数据结构系统的资料,包括题目: Pku acm 3253 Fence Repair Pku acm 1861 NetWork Pku acm 2485 Highways Pku acm 1258 Agri...
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj 2763 程序 线段树 LCA 2000MS AC