作者:乐檬 | 来源:互联网 | 2023-05-17 16:01
首先说明这是一个坑!因为发现啊次小生成树为什不用树链剖分写(虽然麻烦但是思路各种清晰!),最小度限制生成树可以用lct写(而且是似乎要比那个直接写的算法容易因为要各种建边删边dfs(就没有考虑过
首先说明这是一个坑!
因为发现啊次小生成树为什不用树链剖分写(虽然麻烦但是思路各种清晰!),最小度限制生成树可以用lct写(而且是似乎要比那个直接写的算法容易因为要各种建边删边dfs(就没有考虑过时间么)!!!!)!!!(好像是错的)
(因为是自己傻叉写不出来)
(半小时后觉得还是自己傻叉了……下面那个代码应该继续敲就行了,一个是最小生成树还没快排,然后在求最小度限制生成树时用邻接矩阵比较简单(反正时间复杂度也是o(n²)),然后每次就直接dfs一遍,dfs的时候传两个参,一个是这个节点,一个是父亲节点,这样方便待会直接在邻接矩阵里面删点。然后真的就是暴力for一边(这样不就不如lct?)枚举下哪个点是和源点相连且边还没被用过的且边值<原树到这个点的值)
然后找了一下题似乎特别特别少!为了个无聊的东西砸了两天太不值得了!所以弃坑!!!!(gdoi只剩137天但是我还在浪费时间……)
然后就把敲一半的失败的程序发上来吧!
function find(s:string):longint;
var
i,u:longint;
begin
u:=1;
for i:=1 to length(s) do begin
if trie[u][s[i]]=0 then begin
inc(total);
trie[u][s[i]]:=total;
end;
u:=trie[u][s[i]];
end;
if hash[u]=0 then begin
inc(tot);
hash[u]:=tot;
end;
exit(hash[u]);
end;
procedure qsort(l,r:longint);
var
i,j,k,mid:longint;
begin
i:=l;
j:=r;
mid:=root[random(r-l)+l].value;
repeat
while root[i].valuedo
inc(i);
while root[j].value>mid
do dec(j);
if i<=j
then begin
swap(root[i].value,root[j].value);
swap(root[i].too,root[j].too);
inc(i);
dec(j);
end;
until i>
j;
if i
then qsort(i,r);
if lthen qsort(l,j);
end;
procedure into;
var
ss,s:string;
i,j:longint;
begin
readln(n);
tot:=0;
ss:='Park';
find(ss);
for i:=1 to n do begin
readln(s);
j:=1;
while s[j]<>' ' do inc(j);
name1:=find(copy(s,1,j-1));
delete(s,1,j);
j:=1;
while s[j]<>' ' do inc(j);
name2:=find(copy(s,1,j-1));
delete(s,1,j);
val(s,j);
if name1>nam2 then swap(name1,name2);
if name1=1 then begin
inc(tot1);
root[tot1].too:=name2;
root[tot1].value:=j;
end
else add1(name1,name2,j);
end;
qsort(1,tot1);
for i:=1 to tot do fa[i]:=i;
readln(m);
end;
procedure work;
begin
for i:=1 to tot2 then
while e[i] do
if find(too1)<>find(too2) then begin
sum:=sum+value;
fa[find(too1)]:=too2;
add2(too1,too2);
add2(too2,too1);
end;
sum1:=0;
for i:=1 to tot1 do
with root[i] do
if find(too)<>i then begin
inc(sum1);
add2(i,too);
sum:=sum+value;
fa[find(too)]:=i;
end;
if sum1>m then begin
writeln('worry');
exit;
end;
if sum1=m then begin
writeln(sum);
exit;
end;
ans:=sum;
for i:=1 to n do d[i]:=mm;
d[1]:=-1;
i:=first[1];
while i<>0 do
while e2[i] do begin
d[too2]:=-1;
i:=next;
end;
dfs(1);
for i:=sum1+1 to m do begin
k:=mm;
l:=0;
for j:=1 to tot1 do
with root[j] do
if (d[too]>0) and (d[too]-value>k) then begin
k:=d[too]-value;
l:=too;
end;
sum:=sum-k;
if sumthen ans:=sum;
fa[max[too]]:=
begin
into;
work;