First question dfs Don't say

Second, it's easy to think of the smallest tree , But I will not , And time complexity doesn't allow

What are the different ways ？

The first thing that comes to mind prim Thought , Let the root node be determined , Other points are undetermined

We're going to continue to extend from the established point , Find the shortest margin to the highest of the undetermined points （ If there are multiple points of the same height , Definitely choose the one with the shortest margin ）

Add margins to ans, And mark this point as OK , Repeat the above , Just know that all the points are fixed .

There's no problem with this algorithm , But complexity still doesn't seem to AC

We want to , Now that we can use something like this prim Thought , Why not Kruska Well ？

Kruskal The problem is , This algorithm does not involve the direction of the edge , You can't choose the solution that meets the condition with this

Before we think about it, we use something like prim When you think about solving problems , The first keyword is the height of the point , Then take the distance as the second keyword

stay Kruskal When sorting the edges , Can we also consider the height of the point as the first keyword , And then sort by distance as the second keyword ？

this is it , Let's take the height of the end point of the edge as the first keyword in descending order , The length is the second keyword in ascending order

Then do it according to the minimum spanning tree method .

It turns out that TLE 了 , Careful comparison of other people's programs, I found that all along my search set is problematic

I used to getfather It's written like this

function getf(x:longint):longint;

begin

while fa[x]<>x do x:=fa[x];

exit(x);

end;

And actually this function is called many times , Obviously, there are a lot of redundant operations

And the right way to write it is

function getf(x:longint):longint;

begin

if fa[x]<>x then fa[x]:=getf(fa[x]);

exit(fa[x]);

end;

This should be the time complexity of the so-called anti Ackermann function

Mend the fold after the sheep have been stolen , It's not too late ;

``` type node=record
x,c,y,next:longint;
end;

var a:array[..] of node;
fa,p,q,h:array[..] of longint;
v:array[..] of boolean;
len,x,y,z,n,m,i,j,k1,k2,t:longint;
ans,e:int64;

procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end;

function getf(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=getf(fa[x]); // alas
exit(fa[x]);
end;

begin
inc(len);
a[len].y:=y;
a[len].c:=z;
a[len].x:=x;
a[len].next:=p[x];
p[x]:=len;
end;

procedure bfs;
var i,f,x,y:longint;
begin
t:=;
q[]:=;
v[]:=true;
f:=;
while f<=t do
begin
x:=q[f];
i:=p[x];
while i<>- do
begin
y:=a[i].y;
if not v[y] then
begin
v[y]:=true;
inc(t);
q[t]:=y;
end;
i:=a[i].next;
end;
inc(f);
end;
end;

procedure sort(l,r:longint);
var i,j,x,y,z:longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ].c;
y:=a[(l+r) shr ].y;
repeat
while (h[a[i].y]>h[y]) or (h[a[i].y]=h[y]) and (a[i].c<x) do inc(i);
while (h[y]>h[a[j].y]) or (h[a[j].y]=h[y]) and (x<a[j].c) do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin
fillchar(p,sizeof(p),);
len:=;
for i:= to n do
for i:= to m do
begin
else begin
end;
end;
bfs;
sort(,len);
for i:= to n do
fa[i]:=i;
i:=;
j:=;
for j:= to len do
begin
if not(v[a[j].x] and v[a[j].y]) then continue;  // First, it has to be accessible points
k1:=getf(a[j].x);
k2:=getf(a[j].y);
if k1<>k2 then
begin
fa[k2]:=k1;
e:=a[j].c;
ans:=ans+e;
inc(i);
end;
end;
writeln(t,' ',ans);
end.```

1. BZOJ2753 SCOI2012 Skiing and time capsule （ Minimum spanning tree ）

First of all, it's obvious that you can take out all the points you can reach and build a new map , So the first question is done . The rest seems to be a bare minimum tree . But obviously this thing is not necessary to learn, and can not run past . Consider the properties of the constructed graph . It can be found that if there is no height ...

2. BZOJ2753 SCOI2012 Skiing and time capsule 【 Minimum spanning tree 】*

BZOJ2753 SCOI2012 Skiing and time capsule Description a180285 I like skiing very much . He came to a snow mountain , There are M Two tracks for taxiing and N The intersection of two orbits ( It's also a scenic spot ), And every attraction has ...

3. BZOJ2753 [SCOI2012] Skiing and time capsule 【kruskal】

Topic link BZOJ2753 Answer key It's over. I'm in the company \(kruskal\) I can't do any naked questions .. The problem is to find the minimum tree graph , The minimum spanning tree of digraph We can't go straight to \(kruskal\), And make sure you add the previous points first , So we're in line ...

4. Bzoj2753 [SCOI2012] Skiing and time capsule

2753: [SCOI2012] Skiing and time capsule Time Limit: 50 Sec  Memory Limit: 128 MBSubmit: 2282  Solved: 796 Descriptio ...

5. [BZOJ2753][SCOI2012] Skiing and time capsule （ Special directed tree graphs ）

subject :http://www.lydsy.com:808/JudgeOnline/problem.php?id=2753 analysis : First question : direct BFS Extension knows it can't be extended Second questions : It looks like the smallest tree = = ...

6. bzoj2753[SCOI2012] Skiing and time capsule Minimum spanning tree

Time Limit: 50 Sec  Memory Limit: 128 MBSubmit: 2843  Solved: 993[Submit][Status][Discuss] Descripti ...

7. 2019.01.17 bzoj2753: [SCOI2012] Skiing and time capsule （ Minimum spanning tree ）

Portal Minimum spanning tree problem . The question : Some directed edges are given , Ask the smallest spanning tree with direction . Ideas : First dfsdfsdfs Save all the useful edges , Then press the endpoint weight as the first keyword , The edge weight is the second key to sort the edges to ensure the legitimacy of the minimum spanning tree , row ...

8. [BZOJ2753] Skiing and time capsule

The first question is to connect the walking edges directly bfs Just once The second question can be similar to kruskal Methods , But the basis of sorting should be changed to the first keyword as the end height ( From big to small ), The second keyword is edge weight ( From small to large ), Just sort the sides that can go Because the same height ...

9. 【bzoj2753】[SCOI2012] Skiing and time capsule

#include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> # ...

## Random recommendation

1. POJ 1061 Frog dating Extended Euclid

Extend Euclidean template and set it A 了 , But pay attention to the time of division , There are comments in the code #include <iostream> #include <cstdio> #include <cs ...

2. win10 Next Solve the system process occupation 80 port

Company computers from win7 Upgrade to win10, Can't start nginx, Output in the log :2016/05/30 09:26:01 [emerg] 7024#5440: bind() to 0.0.0.0:80 failed ...

3. jQuery HTML Node element modification 、 Additional methods html()、append()、prepend()、

Let's start with a code scenario <div>start</div> <p>123</p> <div>end</div> html() operation ...

4. How to install cacti With Nginx

Reproduced in :https://github.com/blackyboy/Ubuntu-Linux-Stuffs/blob/master/How-to-install-Cacti-Monitoring-Ser ...

5. jsp Chain code

6. DX Of .x file

template Header { <3D82AB43-62DA-11cf-AB39-0020AF71E433> WORD major; WORD minor; DWORD flags;} ...

7. --@angularJS-- A simple UI-Router route demo

1.index.html: <!DOCTYPE HTML><html ng-app="routerApp"><head>    <titl ...

8. centos 7.3 Installation configuration python3.6.1

1. First, install some of the dependency problems I encountered ( If you have dependency problems, follow the prompts to install ): yum install xz gcc zlib zlib-devel 2. Download the source package on the official website Address :https://www.python.or ...

9. Resolved validation conflict with readonly

/** * Bug Go around the plan WorkAround * Bug describe : * JQuery Of Validation And form Of input The element is set to readonly, A pair of irreconcilable contradictions : * One is set to requ ...

10. （13flask Continue to study ） Do it yourself , Write a neural network program , solve Mnist problem , And network deployment

solve 3 A question : 1. Let's implement an example by ourselves flask project : 2. stay flask in , How to call json Pass value : 3. Learn more about existing code . Flask In the whole system is as a background framework , External provision api service , So the reason for it is ...