M_sea

洛谷4172 [WC2006]水管局长
LuoguBZOJ数据加强版分析LCT板子题。简化题意,发现有两种操作:断边、询问两点间最小瓶颈路上最小边权。发现...
扫描右侧二维码阅读全文
28
2019/02

洛谷4172 [WC2006]水管局长

Luogu

BZOJ数据加强版

分析

LCT板子题。

简化题意,发现有两种操作:断边、询问两点间最小瓶颈路上最小边权。

发现询问到的路径一定在最小生成树上,于是要维护最小生成树,可以用$\mathrm{LCT}$来做。

然后断边不太好做,可以反过来,变成加边操作。

考虑怎么维护最小生成树。

首先把边看做点。假设第 $i$ 条边连接 $u$ 和 $v$ ,那么在$\mathrm{LCT}$上连接 $(u,i)$ 和 $(v,i)$ 两条边。

现在假设加入了一条 $(x,y)$ 边,它的边权为 $z$。

首先询问 $x$ 到 $y$ 的路径上边权最大的边,假设它的边权为 $w$ 。如果 $z<w$ ,那么用 $(x,y)$ 边替换掉 $(u,v)$ 边会更好,于是断掉原来的两条边,再连上新的两条边即可。

具体实现及细节见代码。

代码

如果要过数据加强板,把 int id[][] 改成 map<pair<int,int>,int> id,再修改一下相关的引用即可。

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=101000+10;


struct Edge { int u,v,w; } e[N];
bool operator <(Edge a,Edge b) { return a.w<b.w; }
struct Query { int op,u,v,id; } q[N];

int id[1010][1010];
int vis[N],ans[N];

struct Link_Cut_Tree {
    int fa[N],ch[N][2],v[N],mx[N],rev[N];
    int sta[N];
    inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
    inline void pushup(int x) {
        mx[x]=v[x];
        if (e[mx[ch[x][0]]].w>e[mx[x]].w) mx[x]=mx[ch[x][0]];
        if (e[mx[ch[x][1]]].w>e[mx[x]].w) mx[x]=mx[ch[x][1]];
    }
    inline void reverse(int x) { swap(ch[x][0],ch[x][1]); rev[x]^=1; }
    inline void pushdown(int x) {
        if (rev[x]) {
            if (ch[x][0]) reverse(ch[x][0]);
            if (ch[x][1]) reverse(ch[x][1]);
            rev[x]=0;
        }
    }
    inline void rotate(int x) {
        int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
        if (nroot(y)) ch[z][ch[z][1]==y]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if (w) fa[w]=y; fa[y]=x,fa[x]=z;
        pushup(y);
    }
    inline void splay(int x) {
        int y=x,z=0; sta[++z]=y;
        while (nroot(y)) sta[++z]=y=fa[y];
        while (z) pushdown(sta[z--]);
        while (nroot(x)) {
            y=fa[x],z=fa[y];
            if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    inline void access(int x) {
        for (re int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x) { access(x); splay(x); reverse(x); }
    inline int findroot(int x) {
        access(x); splay(x);
        while (ch[x][0]) pushdown(x),x=ch[x][0];
        return x;
    }
    inline void split(int x,int y) { makeroot(x); access(y); splay(y); }
    inline void link(int x,int y) { makeroot(x); fa[x]=y; }
    inline void cut(int x,int y) { split(x,y),fa[x]=ch[y][0]=0; }
} T;

int main() {
    int n=read(),m=read(),Q=read();
    for (re int i=1;i<=m;++i) {
        e[i]=(Edge){read(),read(),read()};
        if (e[i].u>e[i].v) swap(e[i].u,e[i].v);
    }
    sort(e+1,e+m+1);
    for (re int i=1;i<=m;++i) id[e[i].u][e[i].v]=i;
    for (re int i=1;i<=Q;++i) {
        q[i]=(Query){read(),read(),read(),0};
        if (q[i].u>q[i].v) swap(q[i].u,q[i].v);
        if (q[i].op==2) {
            int d=id[q[i].u][q[i].v];
            q[i].id=d,vis[d]=1;
        }
    }
    for (re int i=n+1;i<=n+m;++i) T.mx[i]=T.v[i]=i-n;
    for (re int i=1,sum=0;i<=m;++i) {
        if (vis[i]) continue;
        if (sum==n-1) break;
        int u=e[i].u,v=e[i].v;
        if (T.findroot(u)==T.findroot(v)) continue;
        T.link(u,i+n),T.link(v,i+n),++sum;
    }
    for (re int i=Q;i>=1;--i) {
        int u=q[i].u,v=q[i].v;
        if (q[i].op==1) T.split(u,v),ans[i]=e[T.mx[v]].w;
        else {
            T.split(u,v);
            int now=q[i].id,pre=T.mx[v];
            if (e[now].w<e[pre].w) {
                T.cut(u,pre+n),T.cut(v,pre+n);
                T.link(u,now+n),T.link(v,now+n);
            }
        }
    }
    for (re int i=1;i<=Q;++i)
        if (q[i].op==1) printf("%d\n",ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 04 PM

发表评论