Problem

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。

Solution

我觉得自己最终算是想出来了这题怎么做 orz

两个权值难维护。因此按 $a_i$ 排序，之后到了满足 $a_i$ 的边就把边加到图中。现在的问题就是查找目前图中 1 到 n 的路径上最大 $b_i$ 的最小值。

维护一个最小生成树即可。即维护整个图为一棵生成树。插入一条边如果形成环，将环上的最大边删去。这样可以保证解不会更差。因为 1 到 n 的路径若经过了最大边，则走另一条路径肯定可以更小。若没经过，则 1 到 n 的路径可以选择不经过新增的边（因为原本这里没有联通，联通之后不走也是一回事），则保证这个路径不会变得更差。

按照这样的贪心想法，用 LCT 来维护这样的操作就行了（找最大边并删去，然后加入新边）。

也不一定要求现在一定是一棵生成树。如果此时 1 跟 n 联通了，split(1,n) 更新一下答案就 OK 了~

然而如何找边删边？
我一开始以为只要把某个边权随便转移到一个点上就 OK 了，结果这样是不行的 orz

按照 xzz 的做法，把边换成点，记录一下边点所连接的两个点，只有边点带上权值就行了~

话说这题绝对比那个国集队的 Tree 要难吧

Code

// Code by ajcxsu
// Problem: magic forest

#include<bits/stdc++.h>
using namespace std;

inline void gn(int &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=3e5+10, M=5e4+10;
struct Node *nil;
struct Node {
    bool tag;
    int ma, val, id;
    Node *f, *ch[2], *man, *u, *v;
    Node(int va=0, int id=0):tag(0), ma(va), val(va), id(id) { 
        u=v=f=ch[0]=ch[1]=nil;
        man=this;
    }
    bool nroot() {
        return f->ch[0]==this || f->ch[1]==this;
    } 
    int dir() {
        if(!nroot()) return -1;
        return f->ch[1]==this;
    }
    void pud() {
        if(!tag) return;
        tag=0;
        swap(ch[0], ch[1]), ch[0]->tag^=1, ch[1]->tag^=1;
    }
    void upd() {
        ma=val, man=this;
        if(ch[0]->ma>ma) ma=ch[0]->ma, man=ch[0]->man;
        if(ch[1]->ma>ma) ma=ch[1]->ma, man=ch[1]->man;
    }
} *nd[N];
void ini() {
    nil=new Node(0);
    nil->u=nil->v=nil->ch[0]=nil->ch[1]=nil->f=nil;
}

void rot(Node *x) {
    Node *y=x->f, *z=y->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=z;
    if(y->dir()!=-1) z->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x;
    y->upd(); 
}

Node* stk[N];
void splay(Node *x) {
    Node *y=x;
    int z=0;
    stk[++z]=y;
    while(y->nroot()) stk[++z]=y=y->f;
    while(z) stk[z--]->pud();
    while(x->nroot()) {
        y=x->f;
        if(!y->nroot()) rot(x);
        else if(y->dir()==x->dir()) rot(y), rot(x);
        else rot(x), rot(x); 
    }
    x->upd();
}

void access(Node *x) {
    Node *y=nil;
    while(x!=nil) {
        splay(x), x->ch[1]=y, x->upd();
        y=x, x=x->f;
    }
}

void makeroot(Node *x) {
    access(x), splay(x);
    x->tag^=1;
}

int fa[N];
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
bool Union(int a, int b) {
    int af=Find(a), bf=Find(b);
    if(af!=bf) fa[af]=bf;
    return af!=bf;
}

void split(Node *x, Node *y) {
    makeroot(x), access(y), splay(y);
}

void link(Node *x, Node *y) {
    makeroot(x); 
    x->f=y;
}
void cut(Node *x, Node *y) {
    split(x,y);
    x->f=y->ch[0]=nil, y->upd(); 
    
}

struct Edge {
    int u,v,b,id;
};
vector<Edge> as[N];

int main() {
    ini();
    int n,m;
    int u,v,a,b;
    gn(n), gn(m);
    for(int i=1;i<=n;i++) nd[i]=new Node(0,i);
    for(int i=1;i<=m;i++) {
        gn(u), gn(v), gn(a), gn(b);
        as[a].push_back({u,v,b,i+M});
        nd[i+M]=new Node(b, i+M);
        nd[i+M]->u=nd[u], nd[i+M]->v=nd[v];
    }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=50000;i++) {
        for(int j=0, len=as[i].size();j<len;j++) {
            u=as[i][j].u, v=as[i][j].v, b=as[i][j].b, a=as[i][j].id;
            if(!Union(u,v)) {
                split(nd[u], nd[v]);
                if(nd[v]->ma>b) {
                    Node *aim=nd[v]->man;
                    cut(aim->u, aim);
                    cut(aim, aim->v);
                    link(nd[u], nd[a]), link(nd[a], nd[v]);
                }
            }
            else link(nd[u], nd[a]), link(nd[a], nd[v]);
        }
        if(Find(1)!=Find(n)) continue;
        split(nd[1], nd[n]);
        ans=min(ans, i+nd[n]->ma);
    }
    if(ans!=0x3f3f3f3f) printf("%d\n", ans);
    else printf("-1\n");
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2387.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆