BZOJ 3669: [Noi2014]魔法森林 [LCT Kruskal

题目描述

为了得到书法大家的真传，小 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 型守护精灵的个数之和。

输入输出格式

输入格式：

输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。注意数据中可能包含重边与自环。

输出格式：

输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不含引号）。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

3 1

1 2 1 1

输出样例#2：

-1

考虑两个权值的MST？
a排序后b无序啊，LCT是可以维护动态加边的MST的啊
这里不会有连通块分开，所以判连通在用个并查集能快一点

还有一种做法，动态加边SPFA，a排序每次加入边权值为b和边的两个端点到队列。。。。。快了1倍多

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define pa t[x].fa

#define lc t[x].ch[0]

#define rc t[x].ch[1]

const int N=15e4+,M=1e5+,INF=1e9;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,Q,type;

struct LCTnode{

    int ch[],fa,rev,w,mx,p;

}t[N];

inline int wh(int x){return t[pa].ch[]==x;}

inline int isRoot(int x){return t[pa].ch[]!=x&&t[pa].ch[]!=x;}

inline void update(int x){

    t[x].p=x;t[x].mx=t[x].w;

    if(t[lc].mx>t[x].mx) t[x].mx=t[lc].mx,t[x].p=t[lc].p;

    if(t[rc].mx>t[x].mx) t[x].mx=t[rc].mx,t[x].p=t[rc].p;

}

inline void rever(int x){

    t[x].rev^=;

    swap(lc,rc);

}

inline void pushDown(int x){

    if(t[x].rev){

        rever(lc);

        rever(rc);

        t[x].rev=;

    }

}

inline void rotate(int x){

    int f=t[x].fa,g=t[f].fa,c=wh(x);

    if(!isRoot(f)) t[g].ch[wh(f)]=x;t[x].fa=g;

    t[f].ch[c]=t[x].ch[c^];t[t[f].ch[c]].fa=f;

    t[x].ch[c^]=f;t[f].fa=x;

    update(f);update(x);

}

int st[N],top;

inline void splay(int x){

    top=;st[++top]=x;

    for(int i=x;!isRoot(i);i=t[i].fa) st[++top]=t[i].fa;

    for(int i=top;i>=;i--) pushDown(st[i]);

    for(;!isRoot(x);rotate(x))

        if(!isRoot(pa)) rotate(wh(x)==wh(pa)?pa:x);

}

inline void Access(int x){

    for(int y=;x;y=x,x=pa){

        splay(x);

        rc=y;

        update(x);

    }

}

inline void MakeR(int x){

    Access(x);splay(x);

    rever(x);

}

inline int FindR(int x){

    Access(x);splay(x);

    while(lc) x=lc;

    return x;

}

inline void Link(int x,int y){

    MakeR(x);

    t[x].fa=y;

}

inline void Cut(int x,int y){

    MakeR(x);Access(y);splay(y);

    t[y].ch[]=t[x].fa=;

    update(y);

}

inline int Que(int x,int y){

    MakeR(x);Access(y);splay(y);

    return t[y].p;

}

struct edge{

    int u,v,a,b;

    bool operator <(const edge &r)const{return a<r.a;}

}e[M];

int ans=INF;

int fa[N];

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void Kruskal(){

    for(int i=;i<=n;i++) fa[i]=i;

    sort(e+,e++m);

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

        int u=e[i].u,v=e[i].v;

        if(find(u)!=find(v)){

            fa[find(u)]=find(v);

            Link(u,i+n),Link(v,i+n);

            t[i+n].w=t[i+n].mx=e[i].b;

            t[i+n].p=i+n;

        }else{

            int p=Que(u,v);

            if(t[p].w>e[i].b){

                Cut(e[p-n].u,p),Cut(e[p-n].v,p);

                Link(u,i+n),Link(v,i+n);

                t[i+n].w=t[i+n].mx=e[i].b;

                t[i+n].p=i+n;

            }

        }

        if(find()==find(n)) ans=min(ans,e[i].a+t[Que(,n)].w);

    }

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();m=read();

    for(int i=;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].a=read(),e[i].b=read();

    Kruskal();

    printf("%d",ans==INF?-:ans);

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=5e4+,M=1e5+,INF=1e9;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m;

struct data{

    int u,v,a,b;

    bool operator <(const data &r)const{return a<r.a;}

}a[M];

struct edge{

    int v,ne,w;

}e[M<<];

int cnt,h[N];

inline void ins(int u,int v,int w){

    cnt++;

    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;

}

int d[N],q[N],head,tail,inq[N];

inline void lop(int &x){if(x==) x=N-;else if(x==N) x=;}

inline void push(int v){

    if(d[v]<d[q[head]]) lop(--head),q[head]=v;

    else q[tail++]=v,lop(tail);

    inq[v]=;

}

void spfa(){

    while(head!=tail){

        int u=q[head++];inq[u]=;lop(head);

        for(int i=h[u];i;i=e[i].ne){

            int v=e[i].v,w=e[i].w;

            if(d[v]>max(d[u],w)){

                d[v]=max(d[u],w);

                if(!inq[v]) push(v);

            }

        }

    }

}

int ans=INF;

void solve(){

    sort(a+,a++m);

    head=tail=;

    memset(d,0x3f,sizeof(d));

    q[tail++]=;d[]=;inq[]=;

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

        ins(a[i].u,a[i].v,a[i].b);

        head=tail=;

        q[tail++]=a[i].u;inq[a[i].u]=;

        q[tail++]=a[i].v;inq[a[i].v]=;

        spfa();

        ans=min(ans,a[i].a+d[n]);

    }

}

int main(int argc, const char * argv[]) {

    n=read();m=read();

    for(int i=;i<=m;i++) a[i].u=read(),a[i].v=read(),a[i].a=read(),a[i].b=read();

    solve();

    printf("%d",ans==INF?-:ans);

}

巴特西

BZOJ 3669: [Noi2014]魔法森林 [LCT Kruskal | SPFA]

题目描述

输入输出格式

输入输出样例

最新文章

热门文章