POJ1797 Heavy Transportation

题意：N个点，M条边，每条边有权值。求一条1号点到N号点的路径，要求使得路径中的边权最小值最大。

分析：最小生成树的思想，不过在对边排序时是从大到小排序，然后从大到小添加边，当1和N刚好联通时，此时加入的边就是最大的最小边。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 int t,n,m,f[1100];
 6 struct edge
 7 {
 8     int u,v,w;
 9 }e[1100000];
10 int cmp(edge a,edge b)
11 {
12     return a.w>b.w;
13 }
14 int find(int k)
15 {
16     if(f[k]==k)return k;
17     else return f[k]=find(f[k]);
18 }
19 int main(void)
20 {
21     scanf("%d",&t);
22     for(int k=1;k<=t;k++)
23     {
24         scanf("%d %d",&n,&m);
25         for(int i=1;i<=n;i++)f[i]=i;
26         for(int i=1;i<=m;i++)
27         {
28             scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);
29         }
30         sort(e+1,e+1+m,cmp);
31         for(int i=1;i<=m;i++)
32         {
33             int fu=find(e[i].u),fv=find(e[i].v);
34             f[fu]=fv;
35             int f1=find(1),fn=find(n);
36             if(f1==fn){
37                 printf("Scenario #%d:
%d

",k,e[i].w);
38                 break;
39             }
40         }
41     }
42     return 0;
43 }