题解 P4172 【[WC2006]水管局长】

devout · 2020-02-27 16:51:35 · 题解

博客内食用更佳

14:30 开始写题

思路：首先这道题我们肯定要倒序操作，因为只有删边，倒序变成加边更好处理，其实这题跟航线规划挺像的。

我们发现，他让走过的道路的最大准备时间最短，那么他走的路径一定是在他的最小生成树上的！所以问题就转化成了lct维护最小生成树

因为这题要维护的是边权，所以我们把边权看成点，比如说一个连接x,y的编号为i的边我们要连接起来就是

link(x,i+n),link(i+n,y);

维护最小生成树的方法，我们考虑如果我们新加进来一条边，那么一定会形成一个环，我们就需要把这个环上的最大的一条边给删掉，所以我们只需要lct维护一下最大值就可以了，注意这里维护的是边权最大的边的编号

如果新加进来的x\ to \ y的边比之前x,y之间路径上的最大边权还要大，就不管他，否则把最大的cut掉，然后把这条边link上

为了记录编号我们可以先排序然后lower_bound一下

而且这道题有个条件，就是保证任何时刻所有点联通，也就是说最后剩下的至少是一棵树了，考虑的情况就少一些

15:00 码完

一测样例，死了qwq

然后发现是我的vis标记打反了

15:15 第一次提交

交上去发现只有10分

代码：

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

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
# define debug puts("QAQ");

typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
const double eps=1e-7;

template <typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,m,q;
int fa[N],son[N][2],_max[N],val[N],st[N];
int out[N],cnt;
int sum;
bool vis[N],tag[N];

struct Edge{
    int x,y,c;
    bool operator < (const Edge &cmp)const{
        if(x==cmp.x)return y<cmp.y;
        return x<cmp.x;
    }
}e[N];

struct querys{
    int x,y,id,opt;
}qr[N];

bool isroot(int x){
    return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}

bool locate(int x){
    return son[fa[x]][1]==x;    
}

void reverse(int x){
    swap(son[x][0],son[x][1]);
    tag[x]^=1;  
}

void update(int x){
    _max[x]=val[x];
    if(e[_max[son[x][0]]].c>e[_max[x]].c)_max[x]=_max[son[x][0]];
    if(e[_max[son[x][1]]].c>e[_max[x]].c)_max[x]=_max[son[x][1]];   
}

void pushdown(int x){
    if(tag[x]){
        if(son[x][0])reverse(son[x][0]);
        if(son[x][1])reverse(son[x][1]);
        tag[x]=0;
    }
}

void rotate(int x){
    int y=fa[x],z=fa[y],side=locate(x);
    fa[x]=z;
    if(!isroot(y))son[z][son[z][1]==y]=x;
    son[y][side]=son[x][side^1];
    if(son[x][side^1])fa[son[y][side]]=y;
    son[x][side^1]=y,fa[y]=x;
    update(y),update(x);    
}

void splay(int x){
    int y=x,top=0;
    st[++top]=y;
    while(!isroot(y))y=fa[y],st[++top]=y;
    while(top)pushdown(st[top--]);
    while(!isroot(x)){
        int y=fa[x];
        if(!isroot(y))rotate(locate(x)==locate(y)?y:x);
        rotate(x);  
    }
    update(x);
}   

void access(int x){
    for(int y=0;x;y=x,x=fa[x])
        splay(x),son[x][1]=y,update(x); 
}

void makeroot(int x){
    access(x),splay(x);
    reverse(x); 
}

int findroot(int x){
    access(x),splay(x);
    while(son[x][0])pushdown(x),x=son[x][0];
    splay(x);
    return x;
}

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

void link(int x,int y){
    makeroot(x);
    fa[x]=y;    
}

void cut(int x,int y){
    split(x,y);
    fa[x]=son[y][0]=0;  
}

int main()
{
    read(n),read(m),read(q);
    Rep(i,1,m){
        read(e[i].x),read(e[i].y),read(e[i].c);
        if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
    }   
    sort(e+1,e+m+1);
    Rep(i,1,q){
        read(qr[i].opt),read(qr[i].x),read(qr[i].y);
        if(qr[i].x>qr[i].y)swap(qr[i].x,qr[i].y);
        if(qr[i].opt==2){
            int _id=lower_bound(e+1,e+m+1,(Edge){qr[i].x,qr[i].y,0})-e;
            qr[i].id=_id;
            vis[_id]=true;
        }
    }
    Rep(i,1,n+m)_max[i]=val[i]=(i<=n?0:(i-n));
    Rep(i,1,m){
        if(sum==n-1)break;
        int x=e[i].x,y=e[i].y;
        if(vis[i])continue;
        if(findroot(x)==findroot(y))continue;
        link(x,i+n),link(i+n,y);
        sum++;      
    }
    _Rep(i,q,1){
        int x=qr[i].x,y=qr[i].y;
        if(qr[i].opt==1)split(x,y),out[++cnt]=e[_max[y]].c;
        else{
            split(x,y);
            int _id=_max[y];
            if(e[qr[i].id].c>e[_id].c)continue;
            cut(e[_id].x,_id+n),cut(_id+n,e[_id].y);
            link(x,qr[i].id+n),link(y,qr[i].id+n);
        }
    }
    _Rep(i,cnt,1)printf("%d\n",out[i]);
    return 0;
}

为什么呢？

16:15 恍然大悟

别问我中间干啥去了

我们考虑我们正常我们的kruskal是怎么做的

我们要按边权排序，而不是x，y

原来错在这里了啊，那么我们改一下排序方式就好了吧

别急，这样的话lower_bound就不好做了

手写二分又死循环了

最后只好用到map大法

16:35 AC

我们用map来映射一下就好啦

AC code：

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

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
# define debug puts("QAQ");

typedef long long ll;
const int N=2e5+5;
const int mod=1e9+7;
const double eps=1e-7;

template <typename T> void read(T &x){
    x=0;int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,m,q;
int fa[N],son[N][2],_max[N],val[N],st[N];
int out[N],cnt;
int sum;
bool vis[N],tag[N];

struct Edge{
    int x,y,c;
    bool operator < (const Edge &cmp)const{
        return c<cmp.c; 
    }
}e[N];

map<pair<int,int>,int> mp;

struct querys{
    int x,y,id,opt;
}qr[N];

bool isroot(int x){
    return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}

bool locate(int x){
    return son[fa[x]][1]==x;    
}

void reverse(int x){
    swap(son[x][0],son[x][1]);
    tag[x]^=1;  
}

void update(int x){
    _max[x]=val[x];
    if(e[_max[son[x][0]]].c>e[_max[x]].c)_max[x]=_max[son[x][0]];
    if(e[_max[son[x][1]]].c>e[_max[x]].c)_max[x]=_max[son[x][1]];   
}

void pushdown(int x){
    if(tag[x]){
        if(son[x][0])reverse(son[x][0]);
        if(son[x][1])reverse(son[x][1]);
        tag[x]=0;
    }
}

void rotate(int x){
    int y=fa[x],z=fa[y],side=locate(x);
    fa[x]=z;
    if(!isroot(y))son[z][son[z][1]==y]=x;
    son[y][side]=son[x][side^1];
    if(son[x][side^1])fa[son[y][side]]=y;
    son[x][side^1]=y,fa[y]=x;
    update(y),update(x);    
}

void splay(int x){
    int y=x,top=0;
    st[++top]=y;
    while(!isroot(y))y=fa[y],st[++top]=y;
    while(top)pushdown(st[top--]);
    while(!isroot(x)){
        int y=fa[x];
        if(!isroot(y))rotate(locate(x)==locate(y)?y:x);
        rotate(x);  
    }
    update(x);
}   

void access(int x){
    for(int y=0;x;y=x,x=fa[x])
        splay(x),son[x][1]=y,update(x); 
}

void makeroot(int x){
    access(x),splay(x);
    reverse(x); 
}

int findroot(int x){
    access(x),splay(x);
    while(son[x][0])pushdown(x),x=son[x][0];
    splay(x);
    return x;
}

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

void link(int x,int y){
    makeroot(x);
    fa[x]=y;    
}

void cut(int x,int y){
    split(x,y);
    fa[x]=son[y][0]=0;  
}

int main()
{
    read(n),read(m),read(q);
    Rep(i,1,m){
        read(e[i].x),read(e[i].y),read(e[i].c);
        if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
    }   
    sort(e+1,e+m+1);
    Rep(i,1,m)mp[make_pair(e[i].x,e[i].y)]=i;
    Rep(i,1,q){
        read(qr[i].opt),read(qr[i].x),read(qr[i].y);
        if(qr[i].x>qr[i].y)swap(qr[i].x,qr[i].y);
        if(qr[i].opt==2){
            int _id=mp[make_pair(qr[i].x,qr[i].y)];//map映射
            qr[i].id=_id;
            vis[_id]=true;
        }
    }
    Rep(i,1,n+m)_max[i]=val[i]=(i<=n?0:(i-n));
    Rep(i,1,m){
        if(sum==n-1)break;
        int x=e[i].x,y=e[i].y;
        if(vis[i])continue;
        if(findroot(x)==findroot(y))continue;
        link(x,i+n),link(i+n,y);
        sum++;      
    }
    _Rep(i,q,1){
        int x=qr[i].x,y=qr[i].y;
        if(qr[i].opt==1)split(x,y),out[++cnt]=e[_max[y]].c;
        else{
            split(x,y);
            int _id=_max[y];
            if(e[qr[i].id].c>e[_id].c)continue;
            cut(e[_id].x,_id+n),cut(_id+n,e[_id].y);
            link(x,qr[i].id+n),link(y,qr[i].id+n);
        }
    }
    _Rep(i,cnt,1)printf("%d\n",out[i]);
    return 0;
}