社区讨论
为什么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 条回复,欢迎继续交流。
正在加载回复...