【NOI2014】魔法森林

为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为 1…n1…n，边标号为1…m1…m。初始时小E同学在 11 号节点，隐士则住在 nn 号节点。小E需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 11 号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。

只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 eiei 包含两个权值 aiai 与 bibi。若身上携带的A型守护精灵个数不少于 aiai，且B型守护精灵个数不少于 bibi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。

输入格式

第1行包含两个整数 n,mn,m，表示无向图共有 nn 个节点，mm 条边。

接下来 mm 行，第 i+1i+1 行包含4个正整数 xi,yi,ai,bixi,yi,ai,bi，描述第 ii 条无向边。其中 xixi 与 yiyi 为该边两个端点的标号，aiai 与 bibi的含义如题所述。

注意数据中可能包含重边与自环。

输出格式

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

样例一

input

output

32

按a从小到大加边，发现出现环时，删掉这个环上的b最大值，lct维护
（然而spfa可过……

#include<queue>

#include<cstdio>

#include<algorithm>

using namespace std;

int read_p,read_ca;

inline int read(){

    read_p=;read_ca=getchar();

    while(read_ca<''||read_ca>'') read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p;

}

struct na{

    int x,y,a,b,ne;

    bool v;

}b[];

int n,m,x,y,a,c,ma=,u[],dis[],ans,num=,l[];

queue <int> q;

const int INF=1e9;

inline void in(int x,int y,int a,int c){b[++num].x=x;b[num].y=y;b[num].a=a;b[num].b=c;b[num].ne=l[x];l[x]=num;}

inline bool cmp(int x,int y){return b[x].a<b[y].a;}

inline int max(int a,int b){return a>b?a:b;}

inline int min(int a,int b){return a<b?a:b;}

bool v[];

inline void pu(int x){

    if (!v[x]) v[x]=,q.push(x);

}

inline void gx(){

    while (!q.empty()){

        x=q.front();q.pop();v[x]=;

        for (y=l[x];y;y=b[y].ne)

        if (b[y].v&&dis[b[y].y]>dis[x]&&dis[b[y].y]>b[y].b) dis[b[y].y]=max(dis[x],b[y].b),pu(b[y].y);

    }

}

int main(){

    register int i,j=;

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

    for (i=;i<=m;i++) x=read(),y=read(),a=read(),c=read(),ma=max(a,ma),in(x,y,a,c),in(y,x,a,c);

    for (i=;i<=num;i++) u[i]=i;

    sort(u+,u++num,cmp);

    for (i=;i<=n;i++) dis[i]=INF;

    ans=INF;

    for (i=;i<=ma;i++){

        if (b[u[j]].a==i) for (;b[u[j]].a==i;j++) b[u[j]].v=,pu(b[u[j]].x),pu(b[u[j]].y);

        gx();

        ans=min(ans,dis[n]+i);

    }

    if (ans==INF) ans=-;printf("%d\n",ans);

}

spfa

#include<cstdio>

#include<algorithm>

#define MN 50001

#define MM 200001

using namespace std;

int read_p,read_ca;

inline int read(){

    read_p=;read_ca=getchar();

    while(read_ca<''||read_ca>'') read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p;

}

struct na{

    int x,y,a,b,ne;

    bool v;

}b[MM];

int n,m,x,mma=,ans,l[MN],ch[MN][],fa[MN],st[MN],ma[MN],lo[MN];

const int INF=1e9;

inline bool cmp(na x,na y){return x.a<y.a;}

inline int max(int a,int b){return a>b?a:b;}

inline int min(int a,int b){return a<b?a:b;}

bool rev[MN];

inline bool isroot(int x){

    return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;

}

inline void pd(int x){

    if (rev[x]) swap(ch[x][],ch[x][]),rev[ch[x][]]^=,rev[ch[x][]]^=,rev[x]=;

}

inline void up(int x){

    pd(x);pd(ch[x][]);pd(ch[x][]);

    if (b[ma[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=ma[ch[x][]];

    if (b[ma[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=ma[ch[x][]];

    if (b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=lo[ch[x][]];

    if (b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=lo[ch[x][]];

}

inline void rot(int x){

    int y=fa[x],kind=ch[y][]==x,t=lo[x];

    if(!isroot(y)) ch[fa[y]][ch[fa[y]][]==y]=x;

    lo[x]=lo[y];

    if (ch[x][!kind]) lo[y]=lo[ch[x][!kind]],lo[ch[x][!kind]]=t;else lo[y]=t;

    fa[x]=fa[y];fa[y]=x;

    ch[y][kind]=ch[x][!kind];

    ch[x][!kind]=y;

    fa[ch[y][kind]]=y;

    up(y);

}

inline void splay(int x){

    int i=x,to=;

    while (!isroot(i)) st[++to]=i,i=fa[i];up(i);

    for (;to;to--) up(st[to]);

    while (!isroot(x)){

        if (isroot(fa[x])) rot(x);else

        if ((ch[fa[x]][]==x)==(ch[fa[fa[x]]][]==fa[x])) rot(fa[x]),rot(x);else rot(x),rot(x);

    }

    up(x);

}

inline void acc(int x){for (int u=;x;x=fa[u=x]) splay(x),ch[x][]=u;}

inline void re(int x){acc(x);splay(x);rev[x]^=;}

inline void in(int k){

    int x=b[k].x,y=b[k].y;

    acc(x);re(y);

    fa[y]=x;ch[x][]=y;lo[y]=k;

}

inline void del(int k){

    int x=b[k].x,y=b[k].y;

    re(x);acc(y);splay(x);

    ch[x][]=fa[y]=lo[y]=;

}

inline int find(int x){acc(x);splay(x);while (ch[x][]) x=ch[x][];return x;}

inline bool qu(int x,int y){

    return find(x)==find(y);

}

inline int que(){

    if (!qu(,n)) return INF;

    re();acc(n);splay(n);return b[ma[n]].b;

}

inline int qam(int x,int y){

    re(x);acc(y);splay(y);

    return ma[y];

}

int main(){

    register int i,j=;

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

    for (i=;i<=m;i++) b[i].x=read(),b[i].y=read(),b[i].a=read(),b[i].b=read(),mma=max(b[i].a,mma);

    sort(b+,b++m,cmp);

    ans=INF;

    for (i=;i<=mma;i++){

        for (;b[j].a==i;j++){

            if (!qu(b[j].x,b[j].y)) in(j);else{

                x=qam(b[j].x,b[j].y);if (b[x].b>b[j].b) del(x),in(j);

            }

        }

        ans=min(ans,que()+i);

    }

    if (ans==INF) ans=-;printf("%d\n",ans);

}

lct

巴特西

【NOI2014】魔法森林

输入格式

输出格式

样例一

input

output

最新文章

热门文章