BruceJay's Blog

BZOJ3669 魔法森林

| Comments

To start with

蒟蒻Bruce看了题解

Problem

Solution

这题要找出一条1号点到n号点的路径S,使得max{a[e]|e∈S}+max{b[e]|e∈S}最大。
将边按a值升序排好,依次加入,维护以b值为关键字的最小生成树,如果1号点和n号点联通了,就可以用当前加入的边与1号点到n号点的链上最大的边权的和来更新答案。
维护这个最小生成树可以用LCT来解决,每次加入边(u,v)时,询问u到v的链上最大边权是否大于当前加入边的边权,如果大于,删去最大的那条边,加入当前边即可。
具体见代码。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 150100;
const int INF = 0x3f3f3f3f;
struct Edge{int u,v,x,y;}a[N];
bool cmp(const Edge& a1,const Edge& a2)
{return a1.x<a2.x;}
int tr[N][2]; int fa[N];
int mx[N]; bool rev[N];
int val[N]; int st[N];
bool rt[N]; int p[N];
int n,m,ans=INF;

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

int Find(int x)
{
    if(p[x]!=x) p[x]=Find(p[x]);
    return p[x];
}

void Pushup(int x)
{
    int l=tr[x][0],r=tr[x][1];
    mx[x]=x;
    if(val[mx[l]]>val[mx[x]]) mx[x]=mx[l];
    if(val[mx[r]]>val[mx[x]]) mx[x]=mx[r];
}

void Pushdown(int x)
{
    int l=tr[x][0],r=tr[x][1];
    if(rev[x]){
        rev[x]^=1; rev[l]^=1; rev[r]^=1;
        swap(tr[x][0],tr[x][1]);
    }
}

void Rotate(int x)
{
    int y=fa[x],z=fa[y];
    int t=tr[y][0]==x?0:1;
    if(rt[y]) rt[y]=false,rt[x]=true;
    else{
        if(tr[z][0]==y) tr[z][0]=x;
        else tr[z][1]=x;
    }
    fa[x]=z; fa[y]=x; fa[tr[x][t^1]]=y;
    tr[y][t]=tr[x][t^1]; tr[x][t^1]=y;
    Pushup(y); Pushup(x);
}

void Splay(int x)
{
    int top=0;
    for(int i=x;i;i=fa[i]) st[++top]=i;
    for(int i=top;i;i--) Pushdown(st[i]);
    while(!rt[x]){
        int y=fa[x];
        if(!rt[y]){
            int z=fa[y];
            if(tr[y][0]==x^tr[z][0]==y) Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
}

void Access(int x)
{
    int t=0;
    for(;x;x=fa[x]){
        Splay(x);
        rt[tr[x][1]]=true;
        tr[x][1]=t;
        rt[tr[x][1]]=false;
        Pushup(x); t=x;
    }
}

void Reverse(int x)
{
    Access(x); Splay(x); rev[x]^=1;
}

void Link(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    tr[y][1]=x; fa[x]=y; rt[x]=false;
    Pushup(y);
}

void Cut(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    tr[y][0]=fa[x]=0; rt[x]=true;
    Pushup(y);
}

int Query(int x,int y)
{
    Reverse(x); Access(y); Splay(y);
    return mx[y];
}

int main()
{
    freopen("3669.in","r",stdin);
    freopen("3669.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=n+m;i++) rt[i]=true;
    for(int i=1;i<=m;i++){
        a[i].u=read(); a[i].v=read();
        a[i].x=read(); a[i].y=read();
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].u,v=a[i].v;
        if(Find(u)==Find(v)){
            int t=Query(u,v);
            if(a[i].y<val[t]){
                Cut(t,a[t-n].u);
                Cut(t,a[t-n].v);
            }
            else{
                if(Find(1)==Find(n)) ans=min(ans,a[i].x+val[Query(1,n)]);
                continue;
            }
        }
        else p[Find(u)]=p[Find(v)];
        val[i+n]=a[i].y; mx[i+n]=a[i].y;
        Link(i+n,u); Link(i+n,v);
        if(Find(1)==Find(n)) ans=min(ans,a[i].x+val[Query(1,n)]);
    }
    if(ans==INF) ans=-1;
    printf("%d",ans);
    return 0;
}

Last but not least

Bruce智商太低了,做不出也是理所当然。

Comments

comments powered by Disqus