Luogu P2387 [NOI2014] magic forest solution

Title Link: P2387 [NOI2014] magic forest

Meaning: each side has edge right a , b a,b a. B two, please 1 1 1 to n n The path of n is such that the passing edge max ⁡ { a } + max ⁡ { b } \max\{a\}+\max\{b\} max{a}+max{b} as small as possible

Because there are a lot of things written below on the idea of solving problems, which leads to some lengthy, so here is a simplified version of the problem solving first

If you don't understand, you can skip this simplified version and look directly at the full version below

Simplified version

Because it is inconvenient to handle it at the same time a , b a,b a. B two-dimensional, we can enumerate a a a then choose smaller ones as much as possible b b b

this b b b must be connected 1 1 1 and n n On the minimum spanning tree of n

Therefore, this problem is a dynamic LCT naked problem with edges

Code behind, time complexity O ( m log ⁡ m ) O(m\log m) O(mlogm)

Full version

The common solution to this "two-dimensional" problem is to enumerate the first dimension and then optimize the second dimension

It doesn't matter if you don't know this routine

First of all, we can see the meaning of this question, the sum of the maximum value and the minimum value. Obviously, we can't determine how large this value is

Seems to be able to split? But on second thought, two points a + b a+b a+b must be wrong

Then two points first a a a another two points b b b (two sets, two points)?

It doesn't seem to work. This b is not a good dichotomy, and the complexity seems to be O ( n log ⁡ 3 n ) O(n\log^3n) O(nlog3n)

That two points a a What about a? Seems to be right a a a this dimension is ordered from small to large, and then a a When a is equal, the second dimension is also sorted from small to large

And every time we test a a When a, put it in a a Go to the left side of a's position (in the array) to see if it's useful

It's better to enumerate directly from small to large a a Where's a!

So we can enumerate a a a. Then I found that if you want to ensure b b b as small as possible

We need to be at all a ' < a a'<a Find a spanning tree from the edge of a '< a

That is, in use a a The minimum spanning forest is built in the graph built by the left edge of a (in the array) (because this subgraph is not necessarily connected)

When this minimum spanning forest becomes an inclusion node 1 1 1 and n n When the minimum spanning tree of n, we can update the answer

Note that here is the updated answer, not the final result, because the final result is the same as it a a There is no direct relationship between the size of a

For example, a=1,b=998244353 and a=2,b=1. Obviously, the latter is smaller

So how to dynamically maintain a minimum spanning tree? We can use LCT

If you can't maintain the minimum spanning tree dynamically by LCT, you can have a look This article

So, in fact, this problem is solved

That is, enumeration a a a. Dynamic maintenance of minimum spanning tree

Time complexity O ( m log ⁡ m ) O(m\log m) O(mlogm)

The code is as follows

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define N (int)(3e5+5)
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
int n,m,ans=INF;
namespace LCT
{
    struct Edge{int u,v,a,b;}e[N];
    int cmp(Edge a,Edge b){return a.a==b.a?a.b<b.b:a.a<b.a;}
    struct node
    {
        int ch[2],id,mx,w,fa,tag;
    }t[N];
    #define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x))
    void pushr(int x)
    {
        swap(t[x].ch[0],t[x].ch[1]);
        t[x].tag^=1;
    }
    void push_up(int x)
    {
        t[x].id=x;t[x].mx=t[x].w;
        if(t[x].ch[0]&&t[t[x].ch[0]].mx>t[x].mx)
            t[x].mx=t[t[x].ch[0]].mx,t[x].id=t[t[x].ch[0]].id;
        if(t[x].ch[1]&&t[t[x].ch[1]].mx>t[x].mx)
            t[x].mx=t[t[x].ch[1]].mx,t[x].id=t[t[x].ch[1]].id;
    }
    void push_down(int x)
    {
        if(t[x].tag)
        {
            if(t[x].ch[0])pushr(t[x].ch[0]);
            if(t[x].ch[1])pushr(t[x].ch[1]);
            t[x].tag^=1;
        }
    }
    void push_all(int x)
    {
        if(!isroot(x))push_all(t[x].fa);
        push_down(x);
    }
    void rotate(int x)
    {
        int y=t[x].fa;
        int z=t[y].fa;
        int k=t[y].ch[1]==x;
        if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;
        t[x].fa=z;
        t[y].ch[k]=t[x].ch[k^1];
        t[t[x].ch[k^1]].fa=y;
        t[x].ch[k^1]=y;
        t[y].fa=x;
        push_up(y);
        push_up(x);
    }
    void splay(int x)
    {
        push_all(x);
        while(!isroot(x))
        {
            int y=t[x].fa;
            int z=t[y].fa;
            if(!isroot(y))
            (t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
            rotate(x);
        }
    }
    void access(int x)
    {
        for(int y=0;x;y=x,x=t[x].fa)
            splay(x),t[x].ch[1]=y,push_up(x);
    }
    void make_root(int x)
    {
        access(x);splay(x);
        pushr(x);
    }
    int find_root(int x)
    {
        access(x);splay(x);
        while(t[x].ch[0])push_down(x),x=t[x].ch[0];
        splay(x);
        return x;
    }
    void split(int x,int y)
    {
        make_root(x);
        access(y);splay(y);
    }
    void link(int x,int y)
    {
        make_root(x);
        if(find_root(y)!=x)t[x].fa=y;
    }
    void cut(int x,int y)
    {
        make_root(x);
        if(find_root(y)==x&&t[y].fa==x&&!t[y].ch[0])
        {
            t[x].ch[1]=t[y].fa=0;
            push_up(x);
        }
    }
    int ck(int x,int y)
    {
        make_root(x);
        return find_root(y)!=x;
    }
}
signed main()
{
    using namespace LCT;
    read(n);read(m);
    for(int i=1; i<=m; i++)
    {
        read(e[i].u);read(e[i].v);
        read(e[i].a);read(e[i].b);
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        int idx=n+i,x=e[i].u,y=e[i].v;
        t[idx].w=e[i].b;
        if(x==y)continue;
        if(ck(x,y))
            link(x,idx),link(idx,y);
        else
        {
            split(x,y);int now=t[y].id;
            if(t[now].mx<=e[i].b)continue;splay(now);
            t[t[now].ch[0]].fa=t[t[now].ch[1]].fa=0;
            link(x,idx);link(idx,y);
        }
        if(!ck(1,n))
        {
            split(1,n);
            ans=min(ans,t[n].mx+e[i].a);
        }
    }
    if(ans==INF)write(-1);
    else write(ans);pc('\n');
    return 0;
}

Reprint, please indicate the source