首页 > 代码库 > BZOJ1050: [HAOI2006]旅行comf

BZOJ1050: [HAOI2006]旅行comf

2024-07-17 08:27:18   224人阅读

1050: [HAOI2006]旅行comf

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1307  Solved: 632
[Submit][Status]

Description

给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。

Input

第一行包含两个正整数，N和M。 下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向公路，车辆必须以速度v在该公路上行驶。 最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速度比最小的路径。s和t不可能相同。

Output

如果景点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

【数据范围】
1< N < = 500
1 < = x, y < = N，0 < v < 30000，x ≠ y
0 < M < =5000

HINT

题解：

如果最小权值定了，那肯定最大权值越小越好，那我们枚举最小权值，用并查集求出在当前状况下最小的最大权值，更新答案即可

正确性应该是显然的吧

代码：

 1 var i,n,m,s,t,xi,yi,flag,xx:longint; 2     x,y,v:array[0..5010] of longint; 3     fa:array[0..510] of longint; 4 function find(a:longint):longint; 5  begin 6  if fa[a]<>a then fa[a]:=find(fa[a]); 7  exit(fa[a]); 8  end; 9 procedure qsort(h,l:longint);10  var i,j,m,temp:longint;11  begin12  i:=h;j:=l;m:=v[(i+j) shr 1];13  repeat14   while v[i]>m do inc(i);15   while v[j]<m do dec(j);16   if i<=j then17    begin18    temp:=x[i];x[i]:=x[j];x[j]:=temp;19    temp:=y[i];y[i]:=y[j];y[j]:=temp;20    temp:=v[i];v[i]:=v[j];v[j]:=temp;21    inc(i);dec(j);22    end;23  until i>j;24  if i<l then qsort(i,l);25  if j>h then qsort(h,j);26  end;27 procedure init;28  begin29  readln(n,m);30  for i:=1 to m do  readln(x[i],y[i],v[i]);31  readln(s,t);32  qsort(1,m);33  end;34 procedure tryy(step:longint);35  var i:longint;36  begin37  for i:=1 to n do fa[i]:=i;38  for i:=step to m do39   begin40   fa[find(x[i])]:=find(y[i]);41   if find(s)=find(t) then42    begin43    inc(flag);44    if flag=1 then45     begin46     xi:=v[step];47     yi:=v[i];48     end49    else50     if (v[step]/v[i]<xi/yi) then51     begin52     xi:=v[step];53     yi:=v[i];54     end;55    exit;56    end;57   end;58  end;59 function gcd(a,b:longint):longint;60  begin61  if b=0 then exit(a) else exit(gcd(b,a mod b));62  end;63 procedure print;64  begin65  xx:=gcd(xi,yi);66  if xx=yi then writeln(xi div yi)67  else writeln(xi div xx,‘/‘,yi div xx);68  end;69 procedure main;70  begin71  for i:=1 to m do tryy(i);72  if flag=0 then writeln(‘IMPOSSIBLE‘)73  else print;74  end;75 begin76  assign(input,‘input.txt‘);assign(output,‘output.txt‘);77  reset(input);rewrite(output);78  init;79  main;80  close(input);close(output);81 end.
View Code

 


联系
我们