洛谷 题解 UVA1395 【苗条的生成树 Slim Span】
2024-09-01 09:56:11
【题意】
给出一个\(n(n<=100)\)个节点的的图，求最大边减最小边尽量小的生成树。
【算法】
\(Kruskal\)
【分析】
首先把边按边权从小到大进行排序。对于一个连续的边集区间\([L,R]\)，如果这些边使得\(n\)个点全部联通，则一定存在一个苗条度不超过\(W[R]-W[L]\)的生成树（其中\(W[i]\)表示排序后第\(i\)条边的权值）。
从小到大枚举\(L\)，对于每个\(L\)，从小到大枚举\(R\)，同时用并查集将新进入\([L,R]\)的边两端的点合并成一个集合，与\(Kruskal\)算法一样。当所有的点都联通是停止枚举\(R\)，换下一个\(L\)(并且把\(R\)重置为\(L\))，继续枚举。
【代码】
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100+10;
const int MAXM=10000+10;
int n,m;
int fa[MAXN];
int maxn,ans=0x3f3f3f3f;
struct Node
{
int u,v,w;
}edge[MAXM];
inline int read()
{
int tot=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
tot=tot*10+c-'0';
c=getchar();
}
return tot;
}
inline bool cmp(Node x,Node y)
{
return x.w<y.w;
}
inline int find(int k)//并查集
{
if(fa[k]==k)return k;
else return fa[k]=find(fa[k]);
}
inline bool kruskal(int k)//判断是否能形成生成树
{
maxn=0;
int tot=0;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=k;i<=m;i++)
{
if(fa[find(edge[i].u)]!=fa[find(edge[i].v)])
{
maxn=edge[i].w;
fa[find(edge[i].u)]=fa[find(edge[i].v)];
tot++;
}
if(tot==n-1)return 1;//如果所有点都联通，则返回true
}
return 0;//否则返回false
}
int main()
{
while(1)
{
ans=0x3f3f3f3f;
n=read();m=read();
if(!n&&!m)break;
for(int i=1;i<=m;i++)
{
edge[i].u=read();
edge[i].v=read();
edge[i].w=read();
}
sort(edge+1,edge+1+m,cmp);//给边进行从小到大排序
for(int i=1;i<=m;i++)//枚举L
{
if(kruskal(i))
{
ans=min(ans,maxn-edge[i].w);//更新最小值
}
}
if(ans!=0x3f3f3f3f)cout<<ans<<endl;
else cout<<-1<<endl;//特判
}
return 0;
}
刘汝佳大法好！
最新文章
- [POJ2892]Tunnel Warfare
- 刚安装完jdk和eclipse需要配置什么？
- 一步一步写算法（之hash表）
- Best Time to Buy and Sell Stock (java)
- 微信小程序开发小记
- UOJ#36. 【清华集训2014】玛里苟斯 线性基
- iOS UIView 选择性倒角
- yum upgrade和yum update的区别
- vue 开发系列（七） 路由配置
- Jenkins-Pipeline 流水线发布
- ios开发之 -- NSData 和 NSString , UIImage 等之间的互转
- Ubuntu18---VMware虚拟机中Ubuntu18.04系统，开机输入密码后无响应黑屏
- Sequelize-nodejs-7-Associations
- linux 同步 rsync的使用——远程服务器同步配置
- 安全 流程服务器开新机器 内外网 iptables 安全组 用户安全root用户的使用.
- table数据跑马灯效果
- 《javascript模式--by Stoyan Stefanov》书摘--基本技巧
- python基础-第十三篇-13.2Web框架之Tornado
- Kotlin 函数和函数表达式
- Spring初学之FactoryBean配置Bean