【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

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

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=0;read_ca=getchar();
    while(read_ca<‘0‘||read_ca>‘9‘) read_ca=getchar();
    while(read_ca>=‘0‘&&read_ca<=‘9‘) read_p=read_p*10+read_ca-48,read_ca=getchar();
    return read_p;
}
struct na{
    int x,y,a,b,ne;
    bool v;
}b[200001];
int n,m,x,y,a,c,ma=0,u[200001],dis[50001],ans,num=0,l[50001];
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[50001];
inline void pu(int x){
    if (!v[x]) v[x]=1,q.push(x);
}
inline void gx(){
    while (!q.empty()){
        x=q.front();q.pop();v[x]=0;
        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=1;
    n=read();m=read();
    for (i=1;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=1;i<=num;i++) u[i]=i;
    sort(u+1,u+1+num,cmp);
    for (i=2;i<=n;i++) dis[i]=INF;
    ans=INF;
    for (i=1;i<=ma;i++){
        if (b[u[j]].a==i) for (;b[u[j]].a==i;j++) b[u[j]].v=1,pu(b[u[j]].x),pu(b[u[j]].y);
        gx();
        ans=min(ans,dis[n]+i);
    }
    if (ans==INF) ans=-1;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=0;read_ca=getchar();
    while(read_ca<‘0‘||read_ca>‘9‘) read_ca=getchar();
    while(read_ca>=‘0‘&&read_ca<=‘9‘) read_p=read_p*10+read_ca-48,read_ca=getchar();
    return read_p;
}
struct na{
    int x,y,a,b,ne;
    bool v;
}b[MM];
int n,m,x,mma=0,ans,l[MN],ch[MN][2],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]][0]!=x&&ch[fa[x]][1]!=x;
}
inline void pd(int x){
    if (rev[x]) swap(ch[x][0],ch[x][1]),rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,rev[x]=0;
}
inline void up(int x){

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

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

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

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

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

}
inline void rot(int x){
    int y=fa[x],kind=ch[y][1]==x,t=lo[x];
    if(!isroot(y)) ch[fa[y]][ch[fa[y]][1]==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=0;
    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]][1]==x)==(ch[fa[fa[x]]][1]==fa[x])) rot(fa[x]),rot(x);else rot(x),rot(x);
    }
    up(x);
}
inline void acc(int x){for (int u=0;x;x=fa[u=x]) splay(x),ch[x][1]=u;}
inline void re(int x){acc(x);splay(x);rev[x]^=1;}
inline void in(int k){
    int x=b[k].x,y=b[k].y;
    acc(x);re(y);
    fa[y]=x;ch[x][1]=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][0]=fa[y]=lo[y]=0;
}
inline int find(int x){acc(x);splay(x);while (ch[x][0]) x=ch[x][0];return x;}
inline bool qu(int x,int y){
    return find(x)==find(y);
}
inline int que(){
    if (!qu(1,n)) return INF;
    re(1);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=1;
    n=read();m=read();
    for (i=1;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+1,b+1+m,cmp);
    ans=INF;
    for (i=1;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=-1;printf("%d\n",ans);
}

lct

时间: 04-14

【NOI2014】魔法森林的相关文章

bzoj 3669: [Noi2014]魔法森林

3669: [Noi2014]魔法森林 Time Limit: 30 Sec  Memory Limit: 512 MB 动点spfa Description 为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士.魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M.初始时小E同学在号节点1,隐士则住在号节点N.小E需要通过这一片魔法森林,才能够拜访到隐士. 魔法森林中居住了一些妖怪.每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击.幸运的

BZOJ 3669: [Noi2014]魔法森林( LCT )

排序搞掉一维, 然后就用LCT维护加边MST. O(NlogN) -------------------------------------------------------------------------------------- #include<cstdio> #include<cctype> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1

NOI2014 魔法森林

3669: [Noi2014]魔法森林 Time Limit: 30 Sec  Memory Limit: 512 MBSubmit: 106  Solved: 62[Submit][Status] Description 为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士.魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M.初始时小E同学在号节点1,隐士则住在号节点N.小E需要通过这一片魔法森林,才能够拜访到隐士. 魔法森林中居住了一些妖怪.

【BZOJ3669】[Noi2014]魔法森林 LCT

[BZOJ3669][Noi2014]魔法森林 Description 为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士.魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M.初始时小E同学在号节点1,隐士则住在号节点N.小E需要通过这一片魔法森林,才能够拜访到隐士. 魔法森林中居住了一些妖怪.每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击.幸运的是,在号节点住着两种守护精灵:A型守护精灵与B型守护精灵.小E可以借助它们的力量,达到自

1685. [NOI2014]魔法森林

1685. [NOI2014]魔法森林 动态SPFA 求两个数的 最优值 我们可以限定一个值 求另一个的最优值 这个题 我们可以 对a排序 每次动态加边 就省去了 每次SPFA的dis和vis数组的清空 cogs上毫无压力 但是在UOJ上有一个额外的测试点 好像专门卡SPFA 毕竟这个正解应该是LCT嘛 1 #include <cctype> 2 #include <cstdio> 3 #include <algorithm> 4 #define max(a,b) a&

bzoj 3669: [Noi2014]魔法森林 动态树

3669: [Noi2014]魔法森林 Time Limit: 30 Sec  Memory Limit: 512 MBSubmit: 363  Solved: 202[Submit][Status] Description 为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士.魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M.初始时小E同学在号节点1,隐士则住在号节点N.小E需要通过这一片魔法森林,才能够拜访到隐士. 魔法森林中居住了一些妖怪

[bzoj3669][Noi2014]魔法森林_LCT_并查集

魔法森林 bzoj-3669 Noi-2014 题目大意:说不明白题意系列++……题目链接 注释:略. 想法:如果只有1个参量的话spfa.dij什么的都上来了. 两个参量的话我们考虑,想将所有的边按照a排序. 如果两个点:它们之间有两条路径,有一条比另一条劣. 那么我们完全可以将另一条弄掉. 排序之后维护生成树. LCT的点维护的是实子树中第二参量的最大值. 如果当前边连接的两点之前不连通,直接连上. 如果联通,我们判断新边的第二参量和两点之间splay的最大参量之间的关系. 如果新边的第二参

【BZOJ】3669: [Noi2014]魔法森林(lct)

http://www.lydsy.com/JudgeOnline/problem.php?id=3669 首先看到题目应该可以得到我们要最小化 min{ max{a(u, v)} + max{b(u, v)} } 两个变量不好做...那么我们约束一个a 即按a从小到大排序,依次加边. 发现当有环出现时,去掉的是环中b最大的边. 证明:因为a是从小到大排序,因此此时答案为 a+max{b(u, v)},显然b越小越好. 然后需要link和cut操作... 脑洞开到这里开不动了...........

noi2014魔法森林

为了得到书法大家的真传,小 E 同学下定决心去拜访住在魔法森林中的隐 士.魔法森林可以被看成一个包含 ?? 个节点 ?? 条边的无向图,节点标号为1,2,3, ... , ??,边标号为 1,2,3, ... , ??.初始时小 E 同学在 1 号节点,隐士则住在 ?? 号节点.小 E 需要通过这一片魔法森林,才能够拜访到隐士.魔法森林中居住了一些妖怪.每当有人经过一条边的时候,这条边上的妖怪 就会对其发起攻击.幸运的是,在 1 号节点住着两种守护精灵:A 型守护精灵与 B 型守护精灵.小 E

【bzoj 3669】[Noi2014]魔法森林

Description 为了得到书法大家的真传,小E同学下定决心去拜访住在魔法森林中的隐士.魔法森林可以被看成一个包含个N节点M条边的无向图,节点标号为1..N,边标号为1..M.初始时小E同学在号节点1,隐士则住在号节点N.小E需要通过这一片魔法森林,才能够拜访到隐士. 魔法森林中居住了一些妖怪.每当有人经过一条边的时候,这条边上的妖怪就会对其发起攻击.幸运的是,在号节点住着两种守护精灵:A型守护精灵与B型守护精灵.小E可以借助它们的力量,达到自己的目的. 只要小E带上足够多的守护精灵,妖怪们