题目链接: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 ;
}

最新文章

  1. vuex2.0.0爬坑记录 -- mutations的第一个参数state不能解构
  2. How do you install mysql-connector-python (development version) through pip?
  3. AngularJS指令的详解
  4. JavaScript笔记——this的取值
  5. QT 使用jsoncpp
  6. HTTP权威指南阅读笔记四:连接管理
  7. 小记:利用递归调用循环寻找MP3文件的方法。
  8. Linux内核中关于内存的数据结构
  9. java通过ftp和sftp上传war包上传到Linux服务器实现自动重启tomcat的脚本代码
  10. thrift总结
  11. 浅谈用java解析xml文档(四)
  12. CentOS忘记root密码的解决方法
  13. 2. SharePoint Online 开发,请联系qq512800530。加好备注。(不要发站内信。。。)
  14. php编程提高执行效率技巧
  15. BIEE基本函数
  16. ST40 自制 JTAG 适配器
  17. A*寻路算法入门(三)
  18. TypeError: object() takes no parameters
  19. Java网络编程--InetAdress类
  20. 累计进度条 PSP

热门文章

  1. Vue : props 使用细节(父组件传递数据给子组件)
  2. Could not load file or assembly &#39;System.Web.Http
  3. IntelliJ IDEA 运行错误:java: Compilation failed: internal java compiler error
  4. Python中的sort() key含义
  5. 书写优雅的shell脚本(插曲) - kill
  6. (bmp格式)用CDialog的OnCtlColor()消息响应处理背景画刷。
  7. 父窗口与iFrame之间调用方法和元素
  8. 用Xtrabackup实现MySQL全库备份与恢复
  9. vmware实现与windows下的共享文件
  10. 洛谷 - P2762 - 太空飞行计划问题 - 最小割