社区讨论

为什么W了,急急急

P2502[HAOI2006] 旅行参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mi6mom27
此快照首次捕获于
2025/11/20 07:23
4 个月前
此快照最后确认于
2025/11/20 07:23
4 个月前
查看原帖
CPP
var
 i,j,n,m,ans,s,e,max,min:longint;
 x,y,z,num:array[1..5000]of longint;
 function root(nn:longint):longint;
  var nnn:longint;
 begin
  nnn:=nn;
  while num[nn]<>nn do
   nn:=num[nn];
  root:=nn;
  nn:=nnn;
  while num[nn]<>nn do
  begin
   nn:=num[nn];
   num[nn]:=root;
  end;
  exit(root);
 end;
 function high(nn:longint):longint;
 begin
  high:=0;
  while num[nn]<>nn do
  begin
   inc(high);
   nn:=num[nn];
  end;
  exit(high);
 end;
 procedure union(xx,yy:longint);
 begin
  if high(xx)<high(yy) then
   num[root(xx)]:=root(yy) else  num[root(yy)]:=root(xx);
 end;
 procedure qsort(l,r:longint);
  var i,j,mid,t:longint;
 begin
  i:=l;j:=r;
  mid:=z[(r+l)div 2];
  repeat
   while z[i]<mid do inc(i);
   while z[j]>mid do dec(j);
   if (i<=j) then
   begin
    t:=x[i]; x[i]:=x[j]; x[j]:=t;
    t:=y[i]; y[i]:=y[j]; y[j]:=t;
    t:=z[i]; z[i]:=z[j]; z[j]:=t;
    inc(i); dec(j);
   end;
  until(i>j);
  if (l<=j) then qsort(l,j);
  if (i<=r) then qsort(i,r);
 end;
 function gcd(a,b:longint):longint;
 var
  c:longint;
 begin
  while b<>0 do
   begin
    c:=a mod b;
    a:=b;
    b:=c;
   end;
  exit(a);
 end;
procedure readd;
begin
 max:=0; min:=maxlongint;
 read(n,m);
 for i:=1 to m do
  read(x[i],y[i],z[i]);
 read(s,e);
 qsort(1,m);
 for i:=1 to n do num[i]:=i;
end;
begin
 readd;
 for j:=m downto 1 do
 begin
  max:=0; min:=maxlongint;
  for i:=1 to n do num[i]:=i;
  for i:=j to m do
   if root(x[i])<>root(y[i]) then
   begin
    if z[i]>max then max:=z[i];
    if z[i]<min then min:=z[i];
    union(x[i],y[i]);
    if root(s)=root(e) then
    begin
      write(max div gcd(max,min));
      if min div gcd(max,min)<>1 then writeln('/',min div gcd(max,min));
      halt;
    end;
   end;
  end;
 write('IMPOSSIBLE');
end.

回复

0 条回复,欢迎继续交流。

正在加载回复...