bzoj 3669 [Noi2014]魔法森林
LCT练习。。
Description
为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
Input
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
Output
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
Sample Input
【输入样例1】
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
【输入样例2】
3 1
1 2 1 1
Sample Output
【输出样例1】
32
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。
【输出样例2】
-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。
HINT
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000
题解
首先按照一个权ai排序，然后从小到大加边。由于1～n的通路一定是一棵生成树，可以用并查集判断两个点是否连通，并且用LCT维护这棵生成树。如果当前边的两个端点连通的话，那么找一下这两个点树链上的最大值bi，如果bi大于当前边的bi，那么就将这个大的砍掉，将这条边加上，否则的话不加边。
加完一条边了之后判断1和n的连通性，如果连通的话更新答案。
判断是否加边的话ai不会对其产生影响，因为如果1-n连通了当前的ai一定是最大的，如果之前就连通了的话之前一定已经更新过答案了。
实现
维护最大值的操作见上一篇
把每个边用n+i的点表示，链接两点就直接链接x到n+i，n+i到y
因为已经排好序了，相当于已经离散化了，a的边权是按编号大小递增的
这样siz里维护的就是数组的下标
我们按b的关键字排序，然后val从n+1到n+m存的各个边的边权
这样的话update就需要每次提取val的值
void update(int x)
{
siz[x]=x;
if (val[siz[ch[x][0]]]>val[siz[x]]) siz[x]=siz[ch[x][0]];
if (val[siz[ch[x][1]]]>val[siz[x]]) siz[x]=siz[ch[x][1]];
}
每次加边前判断一下边的两头是否连通：
不连通就link上，更新并查集
连通的话，找到这条路径上b最大的一条边，断掉，连上这条边。
每次加完边后，判断一下1，n的连通性，更新一下ans
代码
#include <cstdio>
#include <algorithm>
#define N 200050
#define M 200050
using namespace std;
#define read(a) a=getnum()
inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }
int n,m,x,l,y,top=1,f[N],ch[N][2],siz[N],res[N],father[N],val[N],st[N];
char s[10];
struct node{int x,y,a,b;}e[M];
int find(int x){if (x==father[x])return x;else return father[x]=find(father[x]);}
bool comp(node x,node y){return x.a<y.a||(x.a==y.a&&x.b<y.b);}
int max(int x,int y){if (x>y) return x;return y;}
int min(int x,int y){if (x<y) return x;return y;}
void swap(int &a,int &b){int t=a;a=b;b=t;}
void update(int x)
{
siz[x]=x;
if (val[siz[ch[x][0]]]>val[siz[x]]) siz[x]=siz[ch[x][0]];
if (val[siz[ch[x][1]]]>val[siz[x]]) siz[x]=siz[ch[x][1]];
}
void pushdown(int x)
{
if (res[x] && x)
{
if (ch[x][0]) res[ch[x][0]]^=1;
if (ch[x][1]) res[ch[x][1]]^=1;
swap(ch[x][1],ch[x][0]);
res[x]=0;
}
}
int is_root(int x){return ch[f[x]][1]!=x && ch[f[x]][0]!=x;}
int get_son(int x){return ch[f[x]][1]==x;}
void rot(int x)
{
int fa=f[x],fafa=f[fa],k=get_son(x);
if (!is_root(fa))
ch[fafa][ch[fafa][1]==fa]=x;
ch[fa][k]=ch[x][k^1],f[ch[fa][k]]=fa;
ch[x][k^1]=fa,f[fa]=x;
f[x]=fafa;
update(fa);update(x);
}
void splay(int x)
{
st[top]=x;
for (int i=x;!is_root(i);i=f[i])
st[++top]=f[i];
for (l=top,top=1;l!=0;l--) pushdown(st[l]);
for (int fa;!is_root(x);rot(x))
if (!is_root(fa=f[x]))
rot(get_son(x)==get_son(fa)?fa:x);
}
void access(int x)
{
for (int y=0;x;y=x,x=f[x])
splay(x),ch[x][1]=y,update(x);
}
int find_root(int x)
{
access(x),splay(x);
while(ch[x][0])
x=ch[x][0];
return x;
}
void make_root(int x){access(x),splay(x),res[x]^=1;}
void link(int x,int y){make_root(x),f[x]=y,splay(x);}
void cut(int x,int y){make_root(x),access(y),splay(y),ch[y][0]=f[x]=0;}
int query(int x,int y){make_root(x),access(y),splay(y);return siz[y];}
main()
{
read(n);read(m);int ans=0x3f3f3f3f;
for (int i=1;i<=m;++i)
read(e[i].x),read(e[i].y),read(e[i].a),read(e[i].b);
sort(e+1,e+m+1,comp);
for (int i=1;i<=m;++i) val[n+i]=e[i].b;
for (int i=1;i<=n;++i) father[i]=i;
for (int i=1;i<=m;i++)
{
int fx=find(e[i].x),fy=find(e[i].y);
if (fx!=fy)
{
link(e[i].x,n+i);
link(n+i,e[i].y);
father[fx]=fy;
}
else
{
int k=query(e[i].x,e[i].y);
if (val[k]>e[i].b)
{
cut(e[k-n].x,k);
cut(k,e[k-n].y);
link(e[i].x,n+i);
link(n+i,e[i].y);
}
}
if (find(1)==find(n))
ans=min(ans,e[i].a+val[query(1,n)]);
}
ans!=0x3f3f3f3f?printf("%d\n",ans):puts("-1");
}
第二种思路
spfa
我们对a排序，枚举a，对于每一次枚举求b权最大值的最小值即可
跑M遍SPFA肯定超时无误。。。。
这里要用的SPFA的动态加点（边）法 我们每加一条边 就把边的两端点入队 继续SPFA 不用对f数组进行memset
这方法非常快 比LCT好写了不知多少 然后还有剪枝
剪枝1 每加一条边就SPFA自然很浪费 我们发现数据里有a<=30的点 那么很多边的a值会是重复的 我们把a值相同的点统统加入队列 然后SPFA一次解决
剪枝2 对于一条双向边 我们不必向队列中加两个点 我一开始写的是把f值小的加进去 因为小的可以更新大的 后来发现这样还是慢 就直接在主函数中更新f值大的 能更新就加入队列
这里用的堆优化spfa
#include<ctime>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 50500
using namespace std;
inline int getnum() { int ret=0; char c; for(c=getchar(); c<'0' || c>'9'; c=getchar()); for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0'; return ret; }
#define read(a) a=getnum()
struct node{
int to,f,next;
}table[M<<2];
int head[M],tot;
struct edge{
int x,y,a,b;
}e[M<<1];
bool operator <(edge x,edge y)
{
return x.a < y.a ;
}
int n,m,ans=0x3f3f3f3f,f[M],heap[M],pos[M],top;
void push_up(int x)
{
int t=pos[x];
while(t>1&&f[heap[t]]<f[heap[t>>1]])
swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t>>=1;
}
void insert(int x)
{
heap[++top]=x;
pos[x]=top;
push_up(x);
}
void pop()
{
pos[heap[1]]=0;
heap[1]=heap[top];
heap[top--]=0;
pos[heap[1]]=1;
int t=2;
while(t<=top)
{
if(t<top&&f[heap[t]]>f[heap[t+1]])
t++;
if(f[heap[t]]<f[heap[t>>1]])
swap(heap[t],heap[t>>1]),swap(pos[heap[t]],pos[heap[t>>1]]),t<<=1;
else
break;
}
}
void SPFA()
{
int i;
while(top)
{
int x=heap[1];pop();
for(i=head[x];i;i=table[i].next)
if(f[table[i].to]>max(f[x],table[i].f))
{
f[table[i].to]=max(f[x],table[i].f);
if(!pos[table[i].to])
insert(table[i].to);
else
push_up(table[i].to);
}
}
}
void add(int x,int y,int z)
{
table[++tot].to=y;
table[tot].f=z;
table[tot].next=head[x];
head[x]=tot;
}
char c;
main()
{
int i;
read(n);read(m);
for(i=1;i<=m;i++)
read(e[i].x),read(e[i].y),read(e[i].a),read(e[i].b);
sort(e+1,e+m+1);
memset(f,0x3f,sizeof f);
f[1]=0;
for(i=1;i<=m;i++)
{
add(e[i].x,e[i].y,e[i].b);
add(e[i].y,e[i].x,e[i].b);
if(f[e[i].x]>f[e[i].y])
swap(e[i].x,e[i].y);
if(max(f[e[i].x],e[i].b)<f[e[i].y])
f[e[i].y]=max(f[e[i].x],e[i].b),insert(e[i].y);
if(e[i].a!=e[i+1].a)
SPFA();
ans=min(ans,e[i].a+f[n]);
}
if(ans==0x3f3f3f3f)
puts("-1");
else
printf("%d\n",ans);
}
luogu效率第一，超第二400ms+
bzoj第九名