首页 > 代码库 > 次小生成树 最小度限制生成树
次小生成树 最小度限制生成树
首先说明这是一个坑！
因为发现啊次小生成树为什不用树链剖分写（虽然麻烦但是思路各种清晰！），最小度限制生成树可以用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].value<mid do 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<r then qsort(i,r); if l<j then 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 sum<ans then ans:=sum; fa[max[too]]:=begin into; work;
次小生成树 最小度限制生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。