NOI2014魔法森林题解 (link-cut tree)

总觉得这一题很经典，虽然说spfa算法也能搞定，但是学学link-cut tree挺好。

核心的思想就不多说了，这里大神很多。本人只是想改改代码，使得看起来更加容易一些，把c风格的天书代码转换为良好设计模式的c++风格代码。

这里先留一个目前看得懂的代码，以后上传改好的。

关于zig zag：

zig操作：

        y       x
      /          \ 
     /            \ 
   x       ->       y
    \              /
     z            z

zag操作：

     y                  x
      \                / 
       \              /
         x     ->   y
        /            \
       z              z

注意zig和zag是不改变树链的中序排列的。由于splay操作是一堆zig zag组合，所以splay操作也不会影响树链的中序，这里唯一的问题是reverse操作，会翻转树链中序。

为什么我们需要reverse？这是因为树链中序是有意义的，splay是辅助树，它的中序代表着原来的树中各个结点的实际的深度。 access操作会把该结点变成其所在树链中最深的一个点。所以最效率的表示方法就是把它提到所在splay树的根，然后删掉它的右子结点。一个根结点没有右子结点，这样看来它就是最右的结点啦，即原树链中最深的结点。

然而我们又需要makeroot操作，即把一个结点变为原树链的根结点。这可以借助刚才的access操作。只需要在access之后水平翻转整个splay树，这个根结点就从树链最深的结点变成了最浅的结点，即根结点。实际实现时，大神们发现可以给一个reverse标记即可，不用去当真翻转这个splay树。这个标记会在以后的splay操作中被处理（pushdown）。由于有时候标记会抵消，所以效率还是有提高的。而且这种lazy策略不会做不必要的操作。

总结来说，link cut tree的操作大致如下：

splay：先做未完成的翻转，然后不断的zig zag辅助树。

access：即一个结点舍弃右儿子，然后不断认爹的过程。每个结点都有father指针，但是他的爹原来不认他，没把他当成左孩子或者右孩子。access不断找爹认，当他的右儿子。同时这个当爹的结点享受优惠政策，可以提到树链的根部，并且再帮他认爹，如此继续直到到达整个树的根部。最后一开始的这个结点再进行一个大型找爹之旅，因为现在形成了一整个大的树链，所以splay之后他成为了整个树的根。

makeroot： access + reverse

link：把这个结点当root，再给他安排个爹（虽然爹这时候还没有认这个儿子）

cut：access两个结点，然后断掉连接。

query：一个结点当root，access另一个点，这样他们就在树链的两头，可以得到整个路径的信息。

#include <cstdio>
#include <algorithm>
#include <cstring>
#define M 100005
#define N 50005
#define nil T[0]
#define oo 1000000000
using namespace std;
int n, m;
namespace io {
const int MAXBUF = 1 << 20;
inline char get() {
    static char buf[MAXBUF],*p1,*p2;
    if(p1==p2) {
        p2 = (p1=buf)+fread(buf,1,MAXBUF,stdin);
        if (p1 == p2) return EOF;
    }
    return *p1++;
}

inline void read(int &x) {
   x = 0;
   bool is_neg = false;
    char ch =get();
    while(!(ch >='0' && ch <= '9') && ch != '-') ch = get();
   if (ch == '-') is_neg = true, ch = get();
    while((ch >='0' && ch <= '9')) x = x * 10 + ch  - '0',ch = get();
   if (is_neg) x = -x;
}

inline void read(float &x) {
   x = 0;
   bool is_neg = false;
    char ch =get();
   float basic = 1;
    while(!(ch >='0' && ch <= '9') && ch != '-') ch = get();
   if (ch == '-') is_neg = true, ch = get();
    while((ch >='0' && ch <= '9')) x = x * 10 + ch  - '0',ch = get();
   if (ch == '.') {
      ch = get();
   }
   while((ch >='0' && ch <= '9')) basic *= 0.1, x = x + basic * (ch  - '0'),ch = get();
   if (is_neg) x = -x;
}
}// namespacec io
struct node
{
    bool rev;
    int id, val;
    node *fa, *lc, *rc, *mx;
    node(bool rev = false, int id = 0, int val = 0, 
         node *fa = NULL, node *lc = NULL, node *rc = NULL, node *mx = NULL) :
        rev(rev), id(id), val(val), fa(fa), lc(lc), rc(rc), mx(mx) {}
    inline void update()
    {
        mx = this;
        if(mx -> val < lc -> mx -> val) mx = lc -> mx;
        if(mx -> val < rc -> mx -> val) mx = rc -> mx;
    }
    inline void pushdown()
    {
        if(rev)
        {
            lc -> rev ^= 1; rc -> rev ^= 1;
            swap(lc, rc);
            rev = false;
        }
    }
}*T[M + N], *S[M + N];
void zig(node *x)
{
    node *y = x -> fa;
    y -> lc = x -> rc;
    x -> rc -> fa = y;
    x -> rc = y;
    x -> fa = y -> fa;
    if(y == y -> fa -> lc) y -> fa -> lc = x;
    else if(y == y -> fa -> rc) y -> fa -> rc = x;
    y -> fa = x;
    y -> update();
}
void zag(node *x)
{
    node *y = x -> fa;
    y -> rc = x -> lc;
    x -> lc -> fa = y;
    x -> lc = y;
    x -> fa = y -> fa;
    if(y == y -> fa -> lc) y -> fa -> lc = x;
    else if(y == y -> fa -> rc) y -> fa -> rc = x;
    y -> fa = x;
    y -> update();
}
void splay(node *x)
{
    int top = 0;
    S[top++] = x;
    for(node *i = x; i == i -> fa -> lc || i == i -> fa -> rc; i = i -> fa)
    {
        S[top++] = i -> fa;
    }
    while(top--) S[top] -> pushdown();
    node *y = nil, *z = nil;
    while(x == x -> fa -> lc || x == x -> fa -> rc)
    {
        y = x -> fa; z = y -> fa;
        if(x == y -> lc)
        {
            if(y == z -> lc) zig(y);
            zig(x);
        }
        else
        {
            if(y == z -> rc) zag(y);
            zag(x);
        }
    }
    x -> update();
}
inline void access(node *x)
{
    node*t = x;
    for(node *y = nil; x != nil; y = x, x = x -> fa)
    {
        splay(x);
        x -> rc = y;
        x -> update();
    }
    splay(t);
}
inline void makeroot(node *x)
{
    access(x);  x -> rev ^= 1;
}
inline void lnk(node *x, node *y)
{
    makeroot(x);
    x -> fa = y;
}
inline void cut(node *x, node *y)
{
    makeroot(x);
    access(y); 
    x -> fa = y -> lc = nil;
    y -> update();
}
inline node *find(node *x)
{
    access(x);
    while(x -> lc != nil) x = x -> lc;
    return x;
}
inline node *query(node *x, node *y)
{
    makeroot(x);
    access(y); 
    return y -> mx;
}
struct edge
{
    int u, v, wa, wb;
    edge(int u = 0, int v = 0, int wa = 0, int wb = 0) :u(u), v(v), wa(wa), wb(wb) {}
    inline bool operator < (const edge &b) const
    {
        return wa < b.wa;
    }
}E[M];
int ufs[N];
inline int find(int x) { return x == ufs[x] ? x : ufs[x] = find(ufs[x]); }
int main()
{
#ifndef ONLINE_JUDGE
    freopen("d.txt", "r", stdin);
    freopen("a.txt", "w", stdout);
#endif
    scanf("%d%d", &n, &m);
    nil = new node();
    *nil = node(false, 0, 0, nil, nil, nil, nil);
    for(int i = 1; i <= n + m; ++i) T[i] = new node(false, i, 0, nil, nil, nil, nil);
    for(int i = 1; i <= n; ++i) ufs[i] = i;
    for(int i = 1; i <= m; ++i)
    {
        io::read(E[i].u);
        io::read(E[i].v);
        io::read(E[i].wa);
        io::read(E[i].wb);

    }
    sort(E + 1, E + m + 1);
    for(int i = 1; i <= m; ++i)
    {
        T[n + i] -> val = E[i].wb;
        T[n + i] -> mx = T[n + i];
    }
    int ans = oo;
    for(int i = 1; i <= m; ++i)
    {
        int x = find(E[i].u), y = find(E[i].v);
        if(x != y)
        {
            lnk(T[E[i].u], T[n + i]);
            lnk(T[E[i].v], T[n + i]);
            ufs[x] = y;
        }
        else
        {
            node *t = query(T[E[i].u], T[E[i].v]);
            if(t -> val > E[i].wb)
            {
                cut(T[E[t -> id - n].u], t);
                cut(T[E[t -> id - n].v], t);
                lnk(T[E[i].u], T[n + i]);
                lnk(T[E[i].v], T[n + i]);
            }
        }
        if(find(1) == find(n))
        {
            ans = min(ans, E[i].wa + query(T[1], T[n]) -> val);
        }
    }
    if(ans >= oo) puts("-1");
    else printf("%d\n", ans);
  //  for(int i = 0; i <= n + m; ++i)
 //   {
 //       delete T[i];
 //       T[i] = NULL;
 //   }

    return 0;
}

tendency的博客

博客

评论

发表评论