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

  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

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

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