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; procedure add(x,y,z:longint);

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),);

readln(n,m);

len:=;

for i:= to n do

read(h[i]);

for i:= to m do

begin

readln(x,y,z);

if h[x]>h[y] then add(x,y,z)

else begin

add(y,x,z);

if h[x]=h[y] then add(x,y,z);

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.

## bzoj2753 More articles about

- 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 ...

- 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 ...

- 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 ...

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

- [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 = = ...

- bzoj2753[SCOI2012] Skiing and time capsule Minimum spanning tree
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 2843 Solved: 993[Submit][Status][Discuss] Descripti ...

- 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 ...

- [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 ...

- 【bzoj2753】[SCOI2012] Skiing and time capsule
#include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> # ...

## Random recommendation

- 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 ...

- 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 ...

- 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 ...

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

- jsp Chain code
// Disable caching response.setHeader("Cache-Control", "no-store"); response.setHeader( ...

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

- --@angularJS-- A simple UI-Router route demo
1.index.html: <!DOCTYPE HTML><html ng-app="routerApp"><head> <titl ...

- 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 ...

- 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 ...

- （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 ...