[UOJ]魔法森林[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
explanation
如果小E走路径1→2→4，需要携带19+15=3419+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=3417+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=3619+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=3217+15=32个守护精灵。
综上所述，小E最少需要携带3232个守护精灵。
样例二
input
3 1
1 2 1 1
output
-1
explanation
小E无法从1号节点到达3号节点，故输出-1。
样例三
见样例数据下载
限制与约定
时间限制：3s
空间限制：512MB
下载
思路
非正解：SPFA
用 a的权值排序、加边，用b的权值SPFA松弛
正解：LCT SPLAY
代码
SPFA:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
struct edge { int nxt, to, a, b; };
struct node { int a, b, u, v; };
const int inf = 0x3f3f3f;
const int maxn = 100010;
node line[maxn];
edge e[maxn];
int dis[maxn];
int vis[maxn];
queue<int> q;
int ans = inf;
int head[maxn], cnt = 0;
int cmp(node a, node b) { return a.a < b.a; }
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
void adde(int u, int v, int a, int b){cnt++;e[cnt].to = v; e[cnt].a = a; e[cnt].b = b; e[cnt].nxt = head[u]; head[u] = cnt;}
void SPFA(int st, int ed)
{
vis[st] = 1; vis[ed] = 1;
q.push(st); q.push(ed);
while (!q.empty())
{
int now = q.front();
q.pop();
for (int i = head[now]; i!=-1; i = e[i].nxt)
{
if (dis[e[i].to] > max(dis[now],e[i].b))
{
dis[e[i].to] = max(dis[now], e[i].b);
if (!vis[e[i].to])
{
q.push(e[i].to);
vis[e[i].to] = 1;
}
}
}
vis[now] = 0;
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d %d %d %d", &line[i].u, &line[i].v, &line[i].a, &line[i].b);
}
sort(line + 1, line + m + 1, cmp);
memset(dis, inf, sizeof(dis));
q.push(1);
vis[1] = 1;
dis[1] = 0;
for (int i = 1; i <= m; i++)
{
adde(line[i].u, line[i].v, line[i].a, line[i].b);
adde(line[i].v, line[i].u, line[i].a, line[i].b);
SPFA(line[i].u, line[i].v);
ans = min(ans, dis[n] + line[i].a);
}
printf((ans==inf)?"-1\n":"%d\n",ans);
}
正解LCT(By HJY)
#include<bits/stdc++.h>
#define rep(i,l,r) for(register int i=l;i<=r;++i)
#define rpe(i,r,l) for(register int i=r;i>=l;--i)
#define dyes cerr<<"yes"<<endl
#define pts puts("")
using namespace std;
template <class Type> inline void read(Type &cur){
Type ret=0,flag=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
ret=ret*10+ch-'0';
ch=getchar();
}
cur=ret*flag;
}
typedef long long ll;
const int maxm=2e5+10;
const int maxn=2e5+10;
struct node{
int u,v,a,b;
bool operator < (const node x)const{
if(a==x.a)
return b<x.b;
return a<x.a;
}
}e[maxm];
int n,m;
int cnt;
inline void swap(int &a,int &b){
int c;c=b;b=a;a=c;
}
inline int max(int a,int b){
return a>b ? a:b;
}
inline int min(int a,int b){
return a<b ? a:b;
}
inline void add(int u,int v,int w,int wb){
e[++cnt].u=u;e[cnt].v=v;e[cnt].a=w;e[cnt].b=wb;
}
struct LCT{
int c[maxn][2],fa[maxn],rev[maxn],mx[maxn],val[maxn],tmp[maxn],pos;
inline int get(int x){return x==c[fa[x]][1];}
inline int isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}
inline void push(int x){
if(rev[x]){
rev[x]=0;swap(c[x][1],c[x][0]);
if(c[x][1]) rev[c[x][1]]^=1;
if(c[x][0]) rev[c[x][0]]^=1;
}
}
inline void upd(int x){
mx[x]=x;
int l=c[x][0],r=c[x][1];
if(val[mx[l]]>val[mx[x]]) mx[x]=mx[l];
if(val[mx[r]]>val[mx[x]]) mx[x]=mx[r];
}
inline void rotate(int x){
int t=fa[x],p=fa[t];int d=get(x);
c[t][d]=c[x][d^1];
if(c[x][d^1]) fa[c[x][d^1]]=t;
fa[x]=p;
if(!isroot(t)) c[p][get(t)]=x;
fa[t]=x;c[x][d^1]=t;upd(t);upd(x);
}
inline void splay(int x){
pos=0;tmp[++pos]=x;
for(int i=x;!isroot(i);i=fa[i])
tmp[++pos]=fa[i];
rpe(i,pos,1) push(tmp[i]);
for(int f=fa[x];!isroot(x);rotate(x),f=fa[x])
if(!isroot(f))
rotate(get(x)==get(f) ? f:x);
}
inline void access(int x){for(int t=0;x;t=x,x=fa[x]) splay(x),c[x][1]=t,upd(x);}
inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}
inline void link(int x,int y){makeroot(x);fa[x]=y;}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline void cut(int x,int y){split(x,y);fa[x]=c[y][0]=0;upd(y);}
inline int query(int x,int y){split(x,y);return mx[y];}
}lct;
int ans=0x7f7f7f7f;
int p[maxn];
inline void init(){
rep(i,1,n)
p[i]=i;
}
inline int find(int x){
return x==p[x] ? x:p[x]=find(p[x]);
}
int main(int argc,const char * argv[]){
read(n);read(m);
rep(i,1,m){
int x,y,a,b;
read(x);read(y);read(a);read(b);
add(x,y,a,b);
}
sort(e+1,e+cnt+1);
init();
rep(i,1,m){
int u=e[i].u,v=e[i].v;
//int a loop
if(find(u)==find(v)){
int t=lct.query(u,v);
if(lct.val[t]>e[i].b){
lct.cut(t,e[t-n].u);
lct.cut(t,e[t-n].v);
}else{
if(find(1)==find(n))
ans=min(ans,e[i].a+lct.val[lct.query(1,n)]);
continue;
}
}else p[find(u)]=find(v);
//add edge as a point
lct.val[n+i]=e[i].b;lct.mx[n+i]=n+i;
lct.link(u,n+i);lct.link(v,n+i);
if(find(1)==find(n))
ans=min(ans,e[i].a+lct.val[lct.query(1,n)]);
}
if(ans==0x7f7f7f7f)
puts("-1");
else
printf("%d\n",ans);
return 0;
}