【最小瓶颈生成树】【最小生成树】【kruscal】bzoj1083 [SCOI2005]繁忙的都市
2024-09-02 10:49:03
本意是求最小瓶颈生成树,但是我们可以证明:最小生成树也是最小瓶颈生成树(其实我不会)。数据范围很小,暴力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 ;
}
最新文章
- 客户有两台windows服务器要做sql server双机切换
- centos 安装mongodb
- shell 脚本技巧
- Eclipse魔法堂:任务管理器
- JVM 1.类的加载、连接、初始化
- SAP研究贴之--发票校验提示移动平均价为负
- ExtJs中实现tree节点,全部是单击展开和收缩效果,和收藏夹点击功能一样
- mysql merge
- linux-多线程
- hdu 2859 (二维dp)
- jQuery获取当前对象标签名称
- python实现希尔排序(已编程实现)
- Struts2思维导图
- Confluence安装部署
- JavaWeb开发中采用FreeMarker生成Excel表格
- hdu4135 Co-prime 容斥原理
- OpenGLES.Functions.Missing.in.OpenGLES1.x
- An existing resource has been found at location D:\Tomcat 7\apache-tomcat-7.0.55\webapps。。。
- Kafka设计解析(十一)Kafka无消息丢失配置
- 在python脚本中设置环境变量,并运行相关应用
热门文章
- Codeforces Round #534 (Div. 2) D. Game with modulo(取余性质+二分)
- POJ2594:Treasure Exploration(Floyd + 最小路径覆盖)
- 普通table表格样式及代码大全
- php spl库的使用(PHP标准库)【摘抄引用】
- 一维和二维ST模板
- bzoj1420/1319 Discrete Root
- 【CodeForces】841D. Leha and another game about graph(Codeforces Round #429 (Div. 2))
- 【洛谷 P1363】幻想迷宫(搜索)
- 类的 propert,classmethod,ataticmethod 方法 与 多态
- codevs 线段树练习ⅠⅡⅢ