[NOI2014] 魔法森林

Description

给定一张图，每条边 \(i\) 的权为 \((a_i,b_i)\)，求一条 \(1 \sim n\) 路径，最小化 \(\max_{i\in P}{a_i} + \max_{i\in P}{b_i}\)

Solution

如果我们限定最大的 \(b_i\) ，那么路径一定在以 \(a_i\) 为权的最小生成树上。

Proof. 考虑反证，假设这条路径中有一条边不在 MST 上，那么这条非树边与树必然形成一个环，很显然用这条边换掉环上任意一条其它边会减小生成树的权值，与最小生成树的条件矛盾。

利用这个性质构造算法。我们从小到大枚举 \(b_i\) 的最大值，依次将边加入树中，同时用 LCT 维护以 \(a_i\) 为边权的最小生成树即可。

维护最小生成树的方法非常简单。利用 LCT 维护树链最大值，当新边 \((u,v,w)\) 加入时，我们考虑如果这条边比树链 \(u \sim v\) 上的最大值小，那么就用它换掉那个最大值的边。因此 LCT 上需要维护最大值以及最大值的位置。

使用 LCT 维护边权通常的做法是对边建点，点权赋为边权，而真实的点则不具有点权。同时维护边的基本信息。

以下阐述为较为具体的实现方式

在本题中，我们可以用编号 \(1 \sim n\) 的点来代表真实点，用编号 \(n+1 \sim n+m\) 的点来代表边，同时在一个结构体数组中以 \((u,v,w)\) 的形式记录边权的基本信息。注意边的编号可以用按照 \(b_i\) 为关键字排序后的代替。

在 LCT 的实现层面上，我们可以姑且忽略这一切，全当作维护树链的最大点权和最大点权点编号。

当我们需要查询 \(u \sim v\) 间的最大边权时，我们只需要在 LCT 上询问即可。

当我们需要删除一条边的时候，我们只需要知道它的编号 \(i\) ，然后断开 \((u_i, n+i)\) 和 \((v_i, n+i)\)

当我们需要加入一条边的时候，我们只需要知道它的编号 \(i\) ，然后连接 \((u_i, n+i)\) 和 \((v_i, n+i)\)

Code

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000000;

int n,m;

struct Edge {

    int u,v,w,b;

    bool operator < (const Edge &x) const {

        return b < x.b;

    }

} e[N];

struct LinkCutTree {

    int top, q[N], ch[N][2], fa[N], rev[N], mx[N], mp[N], val[N];

    inline void pushup(int x) {

        mx[0]=mp[0]=0;

        mx[x] = max(max(mx[ch[x][0]],mx[ch[x][1]]),val[x]);

        if(mx[x] == mx[ch[x][0]])

            mp[x]=mp[ch[x][0]];

        if(mx[x] == mx[ch[x][1]])

            mp[x]=mp[ch[x][1]];

        if(mx[x] == val[x])

            mp[x]=x;

    }

    inline void pushdown(int x) {

        if(!rev[x])

            return;

        rev[ch[x][0]]^=1;

        rev[ch[x][1]]^=1;

        rev[x]^=1;

        swap(ch[x][0],ch[x][1]);

    }

    inline bool isroot(int x) {

        return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;

    }

    inline void rotate(int p) {

        int q=fa[p], y=fa[q], x=ch[fa[p]][1]==p;

        ch[q][x]=ch[p][x^1];

        fa[ch[q][x]]=q;

        ch[p][x^1]=q;

        fa[q]=p;

        fa[p]=y;

        if(y)

            if(ch[y][0]==q)

                ch[y][0]=p;

            else  if(ch[y][1]==q)

                ch[y][1]=p;

        pushup(q);

        pushup(p);

    }

    inline void splay(int x) {

        q[top=1]=x;

        for(int i=x; !isroot(i); i=fa[i])

            q[++top]=fa[i];

        for(int i=top; i; i--)

            pushdown(q[i]);

        for(; !isroot(x); rotate(x))

            if(!isroot(fa[x]))

                rotate((ch[fa[x]][0]==x)==(ch[fa[fa[x]]][0]==fa[x])?fa[x]:x);

    }

    void access(int x) {

        for(int t=0; x; t=x,x=fa[x])

            splay(x),ch[x][1]=t,pushup(x);

    }

    void makeroot(int x) {

        access(x);

        splay(x);

        rev[x]^=1;

    }

    int find(int x) {

        access(x);

        splay(x);

        while(ch[x][0])

            x=ch[x][0];

        return x;

    }

    void split(int x,int y) {

        makeroot(x);

        access(y);

        splay(y);

    }

    void cut(int x,int y) {

        split(x,y);

        if(ch[y][0]==x)

            ch[y][0]=0, fa[x]=0;

    }

    void link(int x,int y) {

        makeroot(x);

        fa[x]=y;

    }

    void setval(int p,int v) {

        val[p]=mx[p]=v;

        mp[p]=p;

    }

    int queryv(int p,int q) {

        split(p,q);

        return mx[q];

    }

    int queryp(int p,int q) {

        split(p,q);

        return mp[q];

    }

} lct;

bool check(int p,int q) {

    return lct.find(p)==lct.find(q);

}

int queryv(int p,int q) {

    return lct.queryv(p,q);

}

int queryp(int p,int q) {

    return lct.queryp(p,q)-n;

}

void link(int i) {

    lct.link(n+i,e[i].u);

    lct.link(n+i,e[i].v);

}

void cut(int i) {

    lct.cut(n+i,e[i].u);

    lct.cut(n+i,e[i].v);

}

int ans = 1e+12;

signed main() {

    scanf("%d%d",&n,&m);

    for(int i=1; i<=m; i++) {

        scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].w,&e[i].b);

    }

    sort(e+1,e+m+1);

    for(int i=1;i<=n;i++) lct.setval(i, 0);

    for(int i=1;i<=m;i++) lct.setval(i+n, e[i].w);

    for(int i=1;i<=m;i++) {

        if(check(e[i].u,e[i].v)) {

            int v=queryv(e[i].u,e[i].v), p=queryp(e[i].u,e[i].v);

            if(v > e[i].w) {

                cut(p);

                link(i);

            }

        }

        else {

            link(i);

        }

        if(check(1,n)) {

            ans = min(ans, queryv(1,n) + e[i].b);

        }

    }

    if(ans < (int)1e+12) cout<<ans<<endl;

    else cout<<-1<<endl;

}

巴特西

[NOI2014] 魔法森林 - Link Cut Tree