本意是求最小瓶颈生成树,但是我们可以证明:最小生成树也是最小瓶颈生成树(其实我不会)。数据范围很小,暴力kruscal即可。

 #include<cstdio>
#include<algorithm>
using namespace std;
struct Edge{int u,v,w;void Read(){scanf("%d%d%d",&u,&v,&w);}}edges[];
bool operator < (const Edge &a,const Edge &b){return a.w<b.w;}
int n,m,fa[],rank[],tot;
void init(){for(int i=;i<=n;i++)fa[i]=i;}
int findroot(int x)
{
if(x==fa[x]) return x;
int rt=findroot(fa[x]);
fa[x]=rt;
return rt;
}
void Union(const int &U,const int &V)
{
if(rank[V]<rank[U]) fa[V]=U;
else
{
fa[U]=V;
if(rank[U]==rank[V]) ++rank[U];
}
}
int main()
{
scanf("%d%d",&n,&m); init();
for(int i=;i<=m;++i) edges[i].Read();
sort(edges+,edges+m+);
for(int i=;i<=m;i++)
{
int f1=findroot(edges[i].u),f2=findroot(edges[i].v);
if(f1!=f2)
{
Union(f1,f2);
tot++;
if(tot==n-)
{
printf("%d %d\n",n-,edges[i].w);
return ;
}
}
}
return ;
}

最新文章

  1. 客户有两台windows服务器要做sql server双机切换
  2. centos 安装mongodb
  3. shell 脚本技巧
  4. Eclipse魔法堂:任务管理器
  5. JVM 1.类的加载、连接、初始化
  6. SAP研究贴之--发票校验提示移动平均价为负
  7. ExtJs中实现tree节点,全部是单击展开和收缩效果,和收藏夹点击功能一样
  8. mysql merge
  9. linux-多线程
  10. hdu 2859 (二维dp)
  11. jQuery获取当前对象标签名称
  12. python实现希尔排序(已编程实现)
  13. Struts2思维导图
  14. Confluence安装部署
  15. JavaWeb开发中采用FreeMarker生成Excel表格
  16. hdu4135 Co-prime 容斥原理
  17. OpenGLES.Functions.Missing.in.OpenGLES1.x
  18. An existing resource has been found at location D:\Tomcat 7\apache-tomcat-7.0.55\webapps。。。
  19. Kafka设计解析(十一)Kafka无消息丢失配置
  20. 在python脚本中设置环境变量,并运行相关应用

热门文章

  1. Codeforces Round #534 (Div. 2) D. Game with modulo(取余性质+二分)
  2. POJ2594:Treasure Exploration(Floyd + 最小路径覆盖)
  3. 普通table表格样式及代码大全
  4. php spl库的使用(PHP标准库)【摘抄引用】
  5. 一维和二维ST模板
  6. bzoj1420/1319 Discrete Root
  7. 【CodeForces】841D. Leha and another game about graph(Codeforces Round #429 (Div. 2))
  8. 【洛谷 P1363】幻想迷宫(搜索)
  9. 类的 propert,classmethod,ataticmethod 方法 与 多态
  10. codevs 线段树练习ⅠⅡⅢ