我们根据高度建图,将无向边转化为有向边
首先对于第一问,直接一个bfs搞定,得到ans1
然后第二问,我们就相当于要求找到一颗最小生成树,
满足相对来说深度小的高度大,也就是要以高度为优先级
假设现在有一种添边的方案(一共添ans1-1条,类似于Kruskal的过程)
那么对于添边,我们可以看做是现有一颗树,通过连接一条边将一个点加入到树里的过程
那么对于添加一个点,假设有一种方案先加入X,然后加入Y,HIGH[X]<HIGH[Y]那么肯定
可以找到另一种添加方式,先加入Y,再加入X,因为Y比X高,也就是既然能先加X,X肯定不
影响Y的合法性,也就是以高度为优先级,保证了合法性
那么我们在做Kruskal 的排序的时候,只需要以点(X——>Y,说的是Y点)的高度为第一关键字,
边长为第二关键字就好了。
后来看了网上别人的思路,上面我写的加边的那一部分,可以通过prim来理解,prim就是现在有一个点的集合
然后在剩下的点里找到距离集合最短的一个点加进来,后面高度优先级的证明类似。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
n, m :int64;
high :array[..] of int64;
pred, succ :array[..] of int64;
len :array[..] of int64;
pre, other, last :array[..] of int64;
l :int64;
que :array[..] of int64;
ans1, ans2 :int64;
flag :array[..] of boolean;
father :array[..] of int64; procedure swap(var a,b:int64);
var
c :int64;
begin
c:=a; a:=b; b:=c;
end; procedure connect(x,y:int64);
begin
inc(l);
pre[l]:=last[x];
last[x]:=l;
other[l]:=y;
end; procedure init;
var
i :longint;
x, y, z :int64; begin
read(n,m);
for i:= to n do read(high[i]);
for i:= to m do
begin
read(x,y,z);
if high[x]<high[y] then swap(x,y);
pred[i]:=x; succ[i]:=y; len[i]:=z;
connect(x,y);
if high[x]=high[y] then connect(y,x);
end;
end; procedure bfs;
var
h, t :int64;
cur :int64;
q, p :int64;
i :longint;
begin
h:=; t:=;
que[]:=;
flag[]:=true;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
while q<> do
begin
p:=other[q];
if not flag[p] then
begin
inc(t);
flag[p]:=true;
que[t]:=p;
end;
q:=pre[q];
end;
end;
ans1:=t;
end; procedure qs(l,h:int64);
var
i, j, xx, yy :int64;
begin
i:=l; j:=h;
xx:=high[succ[(i+j) div ]];
yy:=len[(i+j) div ];
while i<j do
begin
while (high[succ[i]]>xx) or (high[succ[i]]=xx) and (len[i]<yy) do inc(i);
while (high[succ[j]]<xx) or (high[succ[j]]=xx) and (len[j]>yy) do dec(j);
if i<=j then
begin
swap(pred[i],pred[j]);
swap(succ[i],succ[j]);
swap(len[i],len[j]);
inc(i); dec(j);
end;
end;
if i<h then qs(i,h);
if j>l then qs(l,j);
end; function getfather(x:int64):int64;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end; procedure main;
var
a, b, fa, fb :int64;
i :longint; begin
bfs;
for i:= to n do father[i]:=i;
qs(,m);
for i:= to m do
begin
a:=pred[i]; b:=succ[i];
if (not flag[a]) or (not flag[b]) then continue;
fa:=getfather(a); fb:=getfather(b);
if (fa<>fb)then
begin
father[fb]:=fa;
ans2:=ans2+len[i];
end;
end;
writeln(ans1,' ',ans2);
end; begin
init;
main;
end.