2006年
时间限制: 2 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
Z小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。 Z小镇附近共有 N(1<N≤500)个景点(编号为1,2,3,…,N),这些景点被M(0<M≤5000)条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。也许是为了保护该地的旅游资源,Z小镇有个奇怪的规定,就是对于一条给定的公路Ri,任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服,因此大家从一个景点前往另一个景点的时候,都希望选择行使过程中最大速度和最小速度的比尽可能小的路线,也就是所谓最舒适的路线。
输入描述 Input Description
第一行包含两个正整数,N和M。 接下来的M行每行包含三个正整数:x,y和v(1≤x,y≤N,0 最后一行包含两个正整数s,t,表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。
输出描述 Output Description
如果景点s到景点t没有路径,输出“IMPOSSIBLE”。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。
样例输入 Sample Input
样例1 4 2 1 2 1 3 4 2 1 4 样例2 3 3 1 2 10 1 2 5 2 3 8 1 3 样例3 3 2 1 2 2 2 3 4 1 3
样例输出 Sample Output
样例1 IMPOSSIBLE 样例2 5/4 样例3 2
数据范围及提示 Data Size & Hint
N(1<N≤500)
M(0<M≤5000)
Vi在int范围内
思路:变形的Kruskal,题目说我们需要找比值最小的情况,那么我们可以枚举所有边,然后找出它的生成树的最大值。再在这里面找出一个比值最小的就可以了
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int MAXN=10001;
7 int f[MAXN];
8 struct node
9 {
10 int u;
11 int v;
12 int w;
13 }a[MAXN];
14 int num=1;
15 int n,m;
16 int find(int x)
17 {
18 if(f[x]!=x) f[x]=find(f[x]);
19 return f[x];
20 }
21 void unionn(int x,int y)
22 {
23 int fx=find(x);
24 int fy=find(y);
25 f[fx]=fy;
26 }
27 int comp(const node & a,const node & b)
28 {
29 return a.w<b.w;
30 }
31 int gcd(int a,int b)
32 {
33 if(b==0)return a;
34 else return gcd(b,a%b);
35 }
36 int main()
37 {
38 scanf("%d%d",&n,&m);
39 for(int i=1;i<=m;i++)
40 scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
41 int bg,ed;
42 scanf("%d%d",&bg,&ed);
43 sort(a+1,a+m+1,comp);
44 double ans=999999;
45 int ansmaxn,ansminn;
46 for(int i=1;i<=m;i++)
47 {
48 int maxn,minn,flag=0;
49 minn=a[i].w;maxn=a[i].w;
50 for(int k=1;k<=n;k++)f[k]=k;
51 for(int j=i;j<=m;j++)
52 {
53 if(find(a[j].u)!=find(a[j].v))
54 {
55 unionn(a[j].u,a[j].v);
56 maxn=max(a[j].w,maxn);
57 }
58 if(find(bg)==find(ed))
59 {flag=1;break;}
60 }
61 if((double)maxn/(double)minn<ans&&flag==1&&find(bg)==find(ed))
62 {
63 ans=(double)maxn/(double)minn;
64 ansmaxn=maxn;ansminn=minn;
65 }
66 }
67 if(ans==999999)printf("IMPOSSIBLE");
68 else if(ansmaxn%ansminn==0)printf("%d",ansmaxn/ansminn);
69 else printf("%d/%d",ansmaxn/gcd(ansmaxn,ansminn),ansminn/gcd(ansmaxn,ansminn));
70 return 0;
71 }