[bzoj] 3669 NOI2014 魔法森林　||　LCT

原题

copy一篇题解：原链接

将边按照a排序，然后从小到大枚举，加入图中。

在图中用lct维护一棵两点之间b最大值尽量小的生成树。

当加入一条边(u, v)时：

如果(u, v)不连通，则直接加入这条边

如果(u, v)连通且它们间路径上的b最大值大于当前边的b，则删除路径上b最大的边，然后加入当前边。

否则这条边没用。

AC代码：

#include<cstdio>

#include<algorithm>

#define N 150010

#define M 100010

#define inf 0x3f3f3f3f

#define which(u) (ls[fa[(u)]]==(u))

#define isroot(u) (!fa[(u)] || (ls[fa[(u)]]!=(u) && rs[fa[u]]!=(u)))

using namespace std;

int n,m,fa[N],ls[N],rs[N],a[N],val[N],ans=inf,num[N],pcnt;

bool rev[N];

char s[20];

struct hhh

{

    int u,v,a,b,p;

    bool operator < (const hhh &qwq) const

	{

	    if (a==qwq.a) return b<qwq.b;

	    return a<qwq.a;

	}

}e[M];

int Max(int a,int b)

{

    return e[a].b>e[b].b?a:b;

}

void update(int x)

{

    val[x]=Max(Max(val[ls[x]],val[rs[x]]),num[x]);

}

void rotate(int u)

{

    int v=fa[u],w=fa[v],b=which(u)?rs[u]:ls[u];

    if (!isroot(v)) (which(v)?ls[w]:rs[w])=u;

    which(u)?(ls[v]=b,rs[u]=v):(rs[v]=b,ls[u]=v);

    fa[u]=w,fa[v]=u;

    if (b) fa[b]=v;

    update(v);

}

void pushdown(int u)

{

    if (!rev[u]) return ;

    rev[ls[u]]^=1;

    rev[rs[u]]^=1;

    swap(ls[u],rs[u]);

    rev[u]=0;

}

void splay(int u)

{

    static int stk[N],top;

    stk[top=1]=u;

    while (!isroot(stk[top])) stk[top+1]=fa[stk[top]],top++;

    while (top) pushdown(stk[top--]);

    while (!isroot(u))

    {

	if (!isroot(fa[u]))

	{

	    if (which(u)==which(fa[u])) rotate(fa[u]);

	    else rotate(u);

	}

	rotate(u);

    }

    update(u);

}

void access(int u)

{

    int v=0;

    while (u)

    {

	splay(u);

	rs[u]=v;

	v=u;

	u=fa[u];

    }

}

void makeroot(int u)

{

    access(u);

    splay(u);

    rev[u]^=1;

}

int findroot(int x)

{

    access(x);

    splay(x);

    while (pushdown(x),ls[x]) x=ls[x];

    splay(x);

    return x;

}

void link(int u,int v)

{

    makeroot(v);

    fa[v]=u;

}

void cut(int u,int v)

{

    makeroot(u);

    access(v);

    splay(v);

    ls[v]=fa[u]=0;

    update(v);

}

void add(int i)

{

    e[i].p=++pcnt;

    num[e[i].p]=val[e[i].p]=i;

    link(e[i].u,e[i].p);

    link(e[i].v,e[i].p);

}

void erase(int i)

{

    cut(e[i].u,e[i].p);

    cut(e[i].v,e[i].p);

}

int query(int u,int v)

{

    makeroot(u);

    access(v);

    splay(v);

    return val[v];

}

int main()

{

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

    pcnt=n;

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

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

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

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

    {

	if (findroot(e[i].u)!=findroot(e[i].v)) add(i);

	else

	{

	    int mx=query(e[i].u,e[i].v);

	    if (e[mx].b>e[i].b)

		erase(mx),add(i);

	}

	if (findroot(1)==findroot(n))

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

    }

    printf("%d",ans!=inf?ans:-1);

    return 0;

}

巴特西

[bzoj] 3669 NOI2014 魔法森林　||　LCT

原题

最新文章

热门文章

巴特西

[bzoj] 3669 NOI2014 魔法森林 || LCT

原题

最新文章

热门文章

[bzoj] 3669 NOI2014 魔法森林　||　LCT