bzoj 1050: [HAOI2006]旅行comf

 1 program ddk;
 2 type ty=record
 3        x,y,z:longint;
 4       end;
 5 var a:array[1..500]of longint;
 6     b:array[0..5000]of ty;
 7     n,i,j,m,max,max1,min,min1,a1,a2,s,t:longint;
 8 procedure kuai(s,t:longint);
 9   var i,j,p:longint;
10   begin
11     i:=s;
12     j:=t;
13     p:=b[(s+t)div 2].z;
14     repeat
15       while b[i].z<p do
16         inc(i);
17       while b[j].z>p do
18         dec(j);
19       if j>=i
20         then
21           begin
22             b[0]:=b[i];
23             b[i]:=b[j];
24             b[j]:=b[0];
25             inc(i);
26             dec(j);
27           end;
28     until i>j;
29     if i<t
30       then kuai(i,t);
31     if j>s
32       then kuai(s,j);
33   end;
34 function zhao(a1:longint):longint;
35   begin
36     if a[a1]<>a1
37       then
38         begin
39           a[a1]:=zhao(a[a1]);
40           exit(a[a1]);
41         end
42       else exit(a[a1]);
43   end;
44 function gcd(a1,a2:longint):longint;
45   var a3:longint;
46   begin
47     repeat
48       a3:=a1 mod a2;
49       a1:=a2;
50       a2:=a3;
51     until a2=0;
52     exit(a1);
53   end;
54 begin
55   max:=9999999;
56   min:=1;
57   read(n,m);
58   for i:=1 to m do
59     read(b[i].x,b[i].y,b[i].z);
60   kuai(1,m);
61   read(s,t);
62   for i:=1 to m do
63     begin
64       for j:=1 to n do
65         a[j]:=j;
66       max1:=b[i].z;
67       min1:=0;
68       for j:=i downto 1 do
69         begin
70           a1:=zhao(b[j].x);
71           a2:=zhao(b[j].y);
72           a[a2]:=a1;
73           if zhao(s)=zhao(t)
74             then
75               begin
76                 min1:=b[j].z;
77                 break;
78               end;
79         end;
80       if (min1<>0)and(max/min>max1/min1)
81         then
82           begin
83             max:=max1;
84             min:=min1;
85           end;
86     end;
87   if max=9999999
88     then writeln(‘IMPOSSIBLE‘)
89     else
90     if max mod min=0
91      then writeln(max div min)
92      else
93        begin
94          a1:=gcd(max,min);
95          writeln(max div a1,‘/‘,min div a1);
96        end;
97 end.
将边按权值排序之后，从小到大枚举最大边，用并查集维护s，t是否相连，刚相连是跳出，算出比值，不断更新答案