题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=711

分析:枚举速度最大的边,找出能够从S到达T的最大速度,然后求出它们的比值,与已经求出的比值进行比较,如果比之前的比值小,则更新比值,记录此种情况下的最大速度和最小速度,直到枚举到从S不能到达T,跳出循环。求出最大速度和最小速度的比值即可。如果从S可以到达T,说明S和T属于同一个集合,因此可以利用并查集来判断从S是否可以到达T。

代码:

 #include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <iomanip>
#include <queue>
#include <stdlib.h>
using namespace std; #define INF 0x3fffffff int f[];
int n,m; struct lu
{
int start,end,speed;
}num[]; bool cmp(lu a,lu b)
{
return a.speed > b.speed;
} int gcd(int a, int b)
{
while(b != )
{
int r = a % b;
a = b;
b = r;
}
return a;
} void init(int n)
{
for(int i=;i<=n;i++)
f[i]=i;
} int find(int x)
{
if(x==f[x])
return f[x];
f[x]=find(f[x]);
return f[x];
} void Union(int x,int y)
{
int p=find(x);
int q=find(y);
if(p > q)
f[p] = q;
else
f[q] = p;
}
int main()
{
int t;
int a,b,i,j,aa,bb;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(i=;i<m;i++)
scanf("%d %d %d",&num[i].start,&num[i].end,&num[i].speed);
sort(num,num+m,cmp);
scanf("%d %d",&a,&b);
double rate = INF*1.0;
for(i=;i<m;i++){
init(n);
for(j=i;j<m;j++){
if(find(num[j].start)!=find(num[j].end))
Union(num[j].start,num[j].end);
if(find(a)==find(b))
break;
}
if(j==m) break;
int v1=num[i].speed,v2=num[j].speed;
if(v1*1.0 / v2 < rate){
aa=v1,bb=v2;
rate=v1*1.0 / v2;
}
}
if(rate == INF)
printf("IMPOSSIBLE\n");
else if(aa % bb == )
printf("%d\n",aa/bb);
else
printf("%d/%d\n",aa/ gcd(aa,bb),bb/ gcd(aa,bb));
}
}

最新文章

  1. (转)C# XMPP客户端与openfire通信(Matrix Xmpp 授权破解教程)
  2. CRYPTO-MD5
  3. MFC MSBDutyTable下载地址
  4. 字符串匹配的KMP算法——Python实现
  5. JS的构造及其事件注意点总结
  6. 转response.sendRedirect()与request.getRequestDispatcher().forward()区别
  7. 转载:C#实现接口回调
  8. iOS 9的 Universal Links 通用链接使用
  9. PSPInstance Object | Web Python
  10. mybatis---知识点复习
  11. Dom4J生成xml和包含CDATA问题
  12. react实战第一步--搭建项目
  13. Event-Loop In JS
  14. (PMP)解题技巧和典型题目分析(模拟一)
  15. Python-数据库 基本SQL语句
  16. Dependency Walker使用说明 转载
  17. 截取字符串后几位用 length
  18. OpenCV2类批量处理文件夹及文件图像 及批量处理后保存到txt文件
  19. queue模拟
  20. Jquery取得iframe中元素的几种方法(转载)

热门文章

  1. 认识Backbone (二)
  2. Everything中文绿色版在Win7/8/10用不了问题的图文教程,只显示盘符
  3. 每天进步一点点——Linux文件锁编程flock
  4. VS2010或2012中,如何设置代码格式化?
  5. POJ 2756 Autumn is a Genius 采用string大数减法
  6. ZOJ 3795 Grouping(Tarjan收缩点+DAG)
  7. 【高德地图API】从头德国高中生JS API(三)覆盖物——大喊|折线|多边形|信息表|聚合marker|点蚀图|照片覆盖
  8. HDU 3103 Shoring Up the Levees(计算几何 搜寻区域)
  9. C# Socket TCP Server &amp; Client &amp; nodejs client
  10. ASP.NET MVC常见问题解决方法