[BZOJ1050][HAOI2006]旅行comf 枚举+并查集
2024-08-30 13:47:19
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1050
将边排序,枚举边权最小的边,依次加边直到S和T连通,更新答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int inline readint(){
int Num;char ch;
while((ch=getchar())<''||ch>'');Num=ch-'';
while((ch=getchar())>=''&&ch<='') Num=Num*+ch-'';
return Num;
}
int N,M,S,T;
struct EDGE{
int u,v,w;
bool operator < (const EDGE &_)const{
return w<_.w;
}
}edge[];
int fa[];
int inline Getfa(int x){
return fa[x]==x?x:fa[x]=Getfa(fa[x]);
}
int inline Gcd(int a,int b){
return !b?a:Gcd(b,a%b);
}
int main(){
N=readint();
M=readint();
for(int i=;i<=M;i++){
edge[i].u=readint();
edge[i].v=readint();
edge[i].w=readint();
}
sort(edge+,edge++M);
S=readint();
T=readint();
int ansu=,ansd=;
for(int i=;i<=M;i++){
for(int j=;j<=N;j++) fa[j]=j;
int mx;
for(int j=i;j<=M;j++){
int fx=Getfa(edge[j].u),
fy=Getfa(edge[j].v);
if(fx==fy) continue;
mx=edge[j].w;
fa[fx]=fy;
if(Getfa(S)==Getfa(T)) break;
}
if(Getfa(S)!=Getfa(T)) break;
if(mx*ansd<ansu*edge[i].w){
ansu=mx;
ansd=edge[i].w;
}
}
if(ansu==){
puts("IMPOSSIBLE");
return ;
}
int gcd=Gcd(ansu,ansd);
ansu/=gcd;
ansd/=gcd;
if(ansd>) printf("%d/%d\n",ansu,ansd);
else printf("%d\n",ansu);
return ;
}
最新文章
- vuex2.0.0爬坑记录 -- mutations的第一个参数state不能解构
- How do you install mysql-connector-python (development version) through pip?
- AngularJS指令的详解
- JavaScript笔记——this的取值
- QT 使用jsoncpp
- HTTP权威指南阅读笔记四:连接管理
- 小记:利用递归调用循环寻找MP3文件的方法。
- Linux内核中关于内存的数据结构
- java通过ftp和sftp上传war包上传到Linux服务器实现自动重启tomcat的脚本代码
- thrift总结
- 浅谈用java解析xml文档(四)
- CentOS忘记root密码的解决方法
- 2. SharePoint Online 开发,请联系qq512800530。加好备注。(不要发站内信。。。)
- php编程提高执行效率技巧
- BIEE基本函数
- ST40 自制 JTAG 适配器
- A*寻路算法入门(三)
- TypeError: object() takes no parameters
- Java网络编程--InetAdress类
- 累计进度条 PSP
热门文章
- Vue : props 使用细节(父组件传递数据给子组件)
- Could not load file or assembly &#39;System.Web.Http
- IntelliJ IDEA 运行错误:java: Compilation failed: internal java compiler error
- Python中的sort() key含义
- 书写优雅的shell脚本(插曲) - kill
- (bmp格式)用CDialog的OnCtlColor()消息响应处理背景画刷。
- 父窗口与iFrame之间调用方法和元素
- 用Xtrabackup实现MySQL全库备份与恢复
- vmware实现与windows下的共享文件
- 洛谷 - P2762 - 太空飞行计划问题 - 最小割