1001 舒适的路线
NOIP 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范围内
分析 Analysis
这道题解法最小生成树（虽然标了并查集的Tag）
解法不难，但是有点难想。我们需要一条速度变化最小的路径，那么可以把边按边权排序，因此边权相近的边会放在一起，显然一棵生成树可以满足我们的需求。
那么我们枚举最大边，在生成生成树的过程中，只要s和t相连了就可以立刻退出，在这之前维护一个最小边，退出前更新答案。
代码 Code
1 #include2 #include 3 #include 4 #include 5 #define maxn 1000000 6 using namespace std; 7 8 struct edge{ 9 int u,v,len;10 }e[maxn];11 12 bool cmp(const edge &a,const edge &b){13 return a.len < b.len;14 }15 16 int gcd(int a,int b){17 return (!b)?a:gcd(b,a%b);18 }19 20 int pre[maxn],n,m,s,t;21 int find(int x){22 if(!pre[x]) return x;23 else{24 pre[x] = find(pre[x]);25 return pre[x];26 }27 }28 void unite(int u,int v){29 if(find(u) != find(v)){30 pre[find(u)] = find(v);31 }32 }33 void kruskal(){34 sort(e,e+m,cmp);35 36 int gua = 999999999,a,b;37 bool swi = false; 38 int p = m-1;39 40 for(p = m-1;p >= 0;p--){41 memset(pre,0,sizeof(pre));42 int maxx = -999999999;43 int minn = 999999999;44 swi = false;45 for(int i = p;i >= 0;i--){46 int u = e[i].u,v = e[i].v;47 if(find(u) != find(v)){48 unite(u,v);49 maxx = max(e[i].len,maxx);50 minn = min(e[i].len,minn);51 }52 53 if(find(s) == find(t)){54 swi = true;55 break;56 }57 }58 59 if(!swi) break;60 if(maxx-minn < gua){61 gua = maxx-minn,a = maxx,b = minn;62 }63 // if(1.0*maxx/minn > 0) ans = min(ans,1.0*maxx/minn);64 }65 66 67 if(!swi && p == m-1) printf("IMPOSSIBLE");68 else if(a%b == 0) printf("%d",a/b);69 else printf("%d/%d",a/gcd(a,b),b/gcd(a,b));70 71 // printf("\n%d",p);72 }73 74 int main(){75 scanf("%d%d",&n,&m);76 77 for(int i = 0;i < m;i++){78 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].len);79 } 80 81 scanf("%d%d",&s,&t);82 83 kruskal();84 85 return 0;86 }