注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

动态仙人掌 系列题解之四——link-cut cactus  

2014-03-25 00:29:22|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
link-cut cactus
首先我们回忆一下之前的做法——维护仙人掌的一棵生成树,非树边作为原子信息出现。
然后我们维护生成树的方式是用lct。也就是说我们维护一棵树的链剖分。
啊哈!那么我们为什么不能直接维护仙人掌的链剖分?
这样我们就得到了link-cut cactus。(……这样命名应该没问题?)

类比link-cut tree,我们研究一下核心操作access。
当然我们还是像lct一样要找个点当根。
我们规定access(x)就会把x到根的最短路全变为实边。
如果实现了这样一个基础操作,那么很多事情就非常简洁了。最短路查询什么的,换根什么的,打标什么的,想怎么做就怎么做。

那么首先面临的一个难题是,什么是实边,什么是虚边?
对于不在环上的部分,显然延续原来的lct的定义是没问题的。
但是如果有环就没“父亲”这一概念,显得很棘手。
没办法,那么我们就以环为单位进行定义吧。

没有环的话就是普通情况,与lct一样,结点有个preferred child,与之相连的边是实边。
有环的话就是文艺情况。首先由于我们是有根的仙人掌,那么环上肯定有一个离根最近的点,我们称为这个环的根。即,从仙人掌的根往下走碰到的第一个在这个环上的点。
对于一个环它有一个preferred child,从环的根到这个结点的最短路径(如果有多条选任意一条)上的边都是实边。那么还剩下另一半的环,我们称为这个环的额外链。额外链的两端是虚边,其它边均是实边。
下图是一个例子。
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客
当然了,还有个2B情况。我们回想lct里access(x)的过程,一开始就会把x的所有儿子边变为虚边。同理,当我们access一个环的根的时候,就会导致如图所示的2B情况。
注意下面三种情况是不被允许的:
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客

那么我们对于每个环记录一些信息来更方便地操作它。
记录pA为环的根,pB为环的preferred child,pEx是环的额外链的splay树的根结点。
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客
而那两条环上的黑边会作为额外链的firstE和lastE被保存下来。
不过这就让我们不得不注意边界情况:
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客
对于这种情况是没有额外链的,自然地pEx也就为空,这样那条黑边就没人保存了。
我没有想到什么简洁优美和谐统一的方式解决这个问题,于是只好多开个missingE来记录这条边。

那么我们还有没有漏掉什么神奇的地方?有!
换根……
回忆lct的换根:
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客
 
但是我们考虑一棵仙人掌的换根:
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客
于是就悲剧了。
难道说不能换根了?
不,可以换。我们注意到不仅是pEx的顺序变了,连pA和pB也要受影响。不过只要把pA和pB对调就可以了。
接着我们发现,可以在splay中比较pA和pB的先后顺序,如果反了就把环信息中pA和pB指针对调,并且给pEx打上翻转标记即可。

这样就讨论齐全了。
在access的时候,如果发现了环,我们就先调整pA、pB使得它们顺序正确。
后面的事情就简单了:
动态仙人掌 系列题解之四——link-cut cactus - vfleaking - vfleaking的博客
下面给出伪代码。……由于要判断pA和pB的先后顺序……而且还有2B情况和pEx为空的情况过来砸场子……
显得很麻烦的样子 = =

void access(x)
{
for (p = x, q = NULL; p; q = p, p = p->fa)
{
splay(p);
if (p->prevE && p->prevE->cir) // 判断p是否在环上。注意环的根不算作在这个环上。
{
isTogether = false; // 判断是否是2B情况。

cir = p->prevE->cir; // 获取p->prevE所在的环的信息

// 由于p可能在额外链上而之前很狗血地splay了,会导致记录的pEx不正确。
if (cir->pEx && !cir->pEx->isRoot())
cir->pEx = p;

splay(cir->pB);
splay(cir->pA);
if (cir->pB->isRoot()) // 2B情况
{
if (cir->pB->fa != cir->pA) // 如果pA、pB顺序不对则进行调整
{
swap(cir->pA, cir->pB);
if (cir->pEx)
cir->pEx->tag_rev(); // 打上翻转标记
}
}
else // 文艺情况
{
isTogether = true;
splay_until(cir->pB, cir->pA); // 把pB splay到pA下面
if (cir->pA->lc == cir->pB) // 如果pA、pB顺序不对则进行调整
{
rotate(cir->pB); // 一次旋转把pB转成根
swap(cir->pA, cir->pB);
if (cir->pEx)
cir->pEx->tag_rev(); // 打上翻转标记
}
cir->pA->rc = NULL;
cir->pA->nextE = NULL; // 暂时断开pA与下面部分的链接转化为2B情况
}
cir->pB->rc = cir->pEx;

// pEx为空的情况,用missingE补上
cir->pB->nextE = cir->pEx ? cir->pEx->msg.firstE : cir->missingE;
if (cir->pEx)
cir->pEx->fa = cir->pB;
// 这样环就被整个地接了起来成为了一棵splay。

p->splay();

// 比较哪边走比较短,如果不是往左走短就调整一下
if (p->getLcTotL() > p->getRcTotL())

{
p->tag_rev();
p->tag_down();
}
cir->pB = p;
cir->pEx = p->rc; // 把较长的那条变为额外链
cir->missingE = p->rc ? NULL : p->nextE; // pEx为空的情况,用missingE补上
if (cir->pEx)
cir->pEx->fa = NULL;

p->rc = q;
p->nextE = q ? q->msg.firstE : NULL;
p->update();

if (isTogether) // 如果是文艺情况还得把pA接回来
{
cir->pA->rc = p;
cir->pA->nextE = p->msg.firstE;
p->splay();
}
}
else // 普通情况
{
p->rc = q;
p->nextE = q ? q->msg.firstE : NULL;
p->update();
}
}
}


至于多条最短路的情况,可以在环信息里记录pA到pB是否有两条最短路,在access的时维护下。这样在统计信息的时候考虑下就好了。

时间复杂度分析?
不会证splay和lct的时间复杂度请回去补……
显然结点和环的preferred child的切换次数是均摊O(log n)的。这样我们就有access的上界O(log^2n)
但是貌似没办法再使用lct的势能分析了。所以最坏情况也应该是均摊O(log^2n)了。虽然我一时想到什么很好的例子卡到O(log^2n),但是看在这么多次splay的份上不是平方就怪了……
写起来还是比维护生成树法爽多了。
实际效率的话……比维护生成树法略慢一些。还算比较快吧,缩小点数据范围的话估计看不出来了。

下面我把动态仙人掌III的link-cut cactus版贴出来吧。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <climits>
using namespace std;

const int INF = INT_MAX;

const int MaxN = 100000;

inline int getint()
{
char c;
while (c = getchar(), ('0' > c || c > '9') && c != '-');

if (c != '-')
{
int res = c - '0';
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return res;
}
else
{
int res = 0;
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return -res;
}
}

template <class T>
class BlockAllocator
{
private:
static const int BlockL = 10000;

union TItem
{
char rt[sizeof(T)];
TItem *next;
};

TItem *pool, *tail;
TItem *unused;
public:
BlockAllocator()
{
pool = NULL;
unused = NULL;
}

T *allocate()
{
TItem *p;
if (unused)
{
p = unused;
unused = unused->next;
}
else
{
if (pool == NULL)
pool = new TItem[BlockL], tail = pool;
p = tail++;
if (tail == pool + BlockL)
pool = NULL;
}
return (T*)p;
}
void deallocate(T *pt)
{
TItem *p = (TItem*)pt;
p->next = unused, unused = p;
}
};

struct edgeWeight;
struct path_message;
struct lcc_circle;
struct lcc_edge;
struct lcc_message;
struct lcc_node;

struct edgeWeight
{
int wA, wB;

edgeWeight(){}
edgeWeight(const int &_wA, const int &_wB)
: wA(_wA), wB(_wB){}

friend inline bool operator==(const edgeWeight &lhs, const edgeWeight &rhs)
{
return lhs.wA == rhs.wA && lhs.wB == rhs.wB;
}
friend inline bool operator!=(const edgeWeight &lhs, const edgeWeight &rhs)
{
return lhs.wA != rhs.wA || lhs.wB != rhs.wB;
}
};

struct path_message
{
int minLA;
int minWB;

path_message(){}
path_message(const edgeWeight &ew)
: minLA(ew.wA), minWB(ew.wB){}
path_message(const int &_minLA, const int &_minWB)
: minLA(_minLA), minWB(_minWB){}

void setEmpty()
{
minLA = 0;
minWB = INF;
}
void setInvalid()
{
minLA = -1;
minWB = -1;
}
bool valid() const
{
return minLA != -1;
}
void setMultiple()
{
minWB = -1;
}

friend inline path_message operator+(const path_message &lhs, const path_message &rhs)
{
if (lhs.minLA < rhs.minLA)
return lhs;
else if (rhs.minLA < lhs.minLA)
return rhs;
else
return path_message(lhs.minLA, -1);
}
friend inline path_message operator*(const path_message &lhs, const path_message &rhs)
{
return path_message(lhs.minLA + rhs.minLA, min(lhs.minWB, rhs.minWB));
}
};

struct lcc_circle
{
lcc_node *pA, *pB;
lcc_node *pEx;
lcc_edge *missingE;
bool equalL;
};
struct lcc_edge
{
edgeWeight ew;
lcc_circle *cir;

inline lcc_circle *getCir()
{
return this ? this->cir : NULL;
}
};
struct lcc_message
{
path_message pathMsg;
lcc_edge *firstE, *lastE;
bool hasCir;
bool hasMultiplePath;

void rev()
{
swap(firstE, lastE);
}
void coverCir(lcc_circle *cir, bool isSingle)
{
hasCir = !isSingle && cir != NULL;
hasMultiplePath = false;
if (cir && firstE->getCir() != cir && lastE->getCir() != cir)
{
if (cir->equalL)
hasMultiplePath = true;
}
}
void addWB(int delta, bool isSingle)
{
if (!isSingle)
pathMsg.minWB += delta;
}

friend inline lcc_message operator+(const lcc_message &lhs, const lcc_message &rhs)
{
lcc_message res;

assert(lhs.lastE == rhs.firstE);
lcc_edge *e = lhs.lastE;

res.pathMsg = lhs.pathMsg * path_message(e->ew) * rhs.pathMsg;
res.hasMultiplePath = lhs.hasMultiplePath || rhs.hasMultiplePath;
if (e->cir && lhs.firstE->getCir() != e->cir && rhs.lastE->getCir() != e->cir)
{
if (e->cir->equalL)
res.hasMultiplePath = true;
}
res.firstE = lhs.firstE, res.lastE = rhs.lastE;
res.hasCir = lhs.hasCir || e->cir || rhs.hasCir;
return res;
}
};
struct lcc_node
{
lcc_node *fa, *lc, *rc;
lcc_edge *prevE, *nextE;

lcc_message msg;

bool hasRev;
bool hasCoveredCir;
lcc_circle *coveredCir;
int wBDelta;

bool isRoot()
{
return !fa || (fa->lc != this && fa->rc != this);
}

void rotate()
{
lcc_node *x = this, *y = x->fa, *z = y->fa;
lcc_node *b = x == y->lc ? x->rc : x->lc;
x->fa = z, y->fa = x;
if (b)
b->fa = y;
if (z)
{
if (z->lc == y)
z->lc = x;
else if (z->rc == y)
z->rc = x;
}
if (y->lc == x)
x->rc = y, y->lc = b;
else
x->lc = y, y->rc = b;
y->update();
}

void allFaTagDown()
{
int anc_n = 0;
static lcc_node *anc[MaxN];
anc[anc_n++] = this;
for (int i = 0; !anc[i]->isRoot(); i++)
anc[anc_n++] = anc[i]->fa;
for (int i = anc_n - 1; i >= 0; i--)
anc[i]->tag_down();
}
void splay()
{
allFaTagDown();
while (!this->isRoot())
{
if (!fa->isRoot())
{
if ((fa->lc == this) == (fa->fa->lc == fa))
fa->rotate();
else
this->rotate();
}
this->rotate();
}
this->update();
}
void splay_until(lcc_node *target)
{
allFaTagDown();
while (this->fa != target)
{
if (fa->fa != target)
{
if ((fa->lc == this) == (fa->fa->lc == fa))
fa->rotate();
else
this->rotate();
}
this->rotate();
}
this->update();
}

int getLcTotL()
{
if (!prevE)
return 0;
int totL = prevE->ew.wA;
if (lc)
totL += lc->msg.pathMsg.minLA + msg.firstE->ew.wA;
return totL;
}
int getRcTotL()
{
if (!nextE)
return 0;
int totL = nextE->ew.wA;
if (rc)
totL += rc->msg.pathMsg.minLA + msg.lastE->ew.wA;
return totL;
}

void access()
{
for (lcc_node *p = this, *q = NULL; p; q = p, p = p->fa)
{
p->splay();
if (p->prevE && p->prevE->cir)
{
bool isTogether = false;

lcc_circle *cir = p->prevE->cir;
if (cir->pEx && !cir->pEx->isRoot())
cir->pEx = p;

cir->pB->splay(), cir->pA->splay();
if (cir->pB->isRoot())
{
if (cir->pB->fa != cir->pA)
{
swap(cir->pA, cir->pB);
if (cir->pEx)
cir->pEx->tag_rev();
}
}
else
{
isTogether = true;
cir->pB->splay_until(cir->pA);
if (cir->pA->lc == cir->pB)
{
cir->pB->rotate();
swap(cir->pA, cir->pB);
if (cir->pEx)
cir->pEx->tag_rev();
}
cir->pA->rc = NULL, cir->pA->nextE = NULL;
}
cir->pB->rc = cir->pEx, cir->pB->nextE = cir->pEx ? cir->pEx->msg.firstE : cir->missingE;
if (cir->pEx)
cir->pEx->fa = cir->pB;

p->splay();

if (p->getLcTotL() > p->getRcTotL())
p->tag_rev(), p->tag_down();
cir->pB = p;
cir->pEx = p->rc, cir->missingE = p->rc ? NULL : p->nextE;
cir->equalL = p->getLcTotL() == p->getRcTotL();
if (cir->pEx)
cir->pEx->fa = NULL;

p->rc = q, p->nextE = q ? q->msg.firstE : NULL;
p->update();

if (isTogether)
{
cir->pA->rc = p, cir->pA->nextE = p->msg.firstE;
p->splay();
}
}
else
{
p->rc = q, p->nextE = q ? q->msg.firstE : NULL;
p->update();
}
}

this->splay();
}

void makeRoot()
{
this->access();
this->tag_rev(), this->tag_down();
}
lcc_node *findRoot()
{
lcc_node *p = this;
p->access();
while (p->tag_down(), p->lc)
p = p->lc;
p->splay();
return p;
}

void tag_rev()
{
hasRev = !hasRev;
msg.rev();
}
void tag_coverCir(lcc_circle *cir)
{
hasCoveredCir = true;
coveredCir = cir;
msg.coverCir(cir, !lc && !rc);
}
void tag_addWB(int delta)
{
wBDelta += delta;
msg.addWB(delta, !lc && !rc);
}
void tag_down()
{
if (hasRev)
{
swap(lc, rc);
swap(prevE, nextE);

if (lc)
lc->tag_rev();
if (rc)
rc->tag_rev();

hasRev = false;
}
if (hasCoveredCir)
{
if (lc)
{
prevE->cir = coveredCir;
lc->tag_coverCir(coveredCir);
}
if (rc)
{
nextE->cir = coveredCir;
rc->tag_coverCir(coveredCir);
}

hasCoveredCir = false;
}
if (wBDelta != 0)
{
if (lc)
{
prevE->ew.wB += wBDelta;
lc->tag_addWB(wBDelta);
}
if (rc)
{
nextE->ew.wB += wBDelta;
rc->tag_addWB(wBDelta);
}

wBDelta = 0;
}
}
void update()
{
msg.pathMsg.setEmpty();
msg.firstE = prevE, msg.lastE = nextE;
msg.hasCir = false;
msg.hasMultiplePath = false;

if (lc)
msg = lc->msg + msg;
if (rc)
msg = msg + rc->msg;
}
};

int n;
lcc_node lccVer[MaxN + 1];
BlockAllocator<lcc_edge> lccEAllocator;
BlockAllocator<lcc_circle> lccCirAllocator;

void cactus_init()
{
for (int v = 1; v <= n; v++)
{
lcc_node *x = lccVer + v;
x->fa = x->lc = x->rc = NULL;
x->prevE = x->nextE = NULL;
x->hasRev = false;
x->hasCoveredCir = false;
x->wBDelta = 0;
x->update();
}
}

bool cactus_link(int v, int u, int wA, int wB)
{
if (v == u)
return false;

edgeWeight ew(wA, wB);

lcc_node *x = lccVer + v, *y = lccVer + u;
x->makeRoot(), y->makeRoot();

if (x->fa)
{
x->access();
if (x->msg.hasCir)
return false;

lcc_circle *cir = lccCirAllocator.allocate();
lcc_edge *e = lccEAllocator.allocate();
e->ew = ew, e->cir = cir;
cir->pA = y, cir->pB = x, cir->pEx = NULL;
cir->missingE = e;
x->tag_coverCir(cir);

x->access();
}
else
{
lcc_edge *e = lccEAllocator.allocate();
e->ew = ew, e->cir = NULL;
x->fa = y, x->prevE = e, x->update();
}
return true;
}
bool cactus_cut(int v, int u, int wA, int wB)
{
if (v == u)
return false;

edgeWeight ew(wA, wB);

lcc_node *x = lccVer + v, *y = lccVer + u;
if (x->findRoot() != y->findRoot())
return false;

y->makeRoot(), x->access();
y->splay_until(x);

lcc_circle *cir = x->prevE->cir;
if (cir && cir->pA == y && !cir->pEx && cir->missingE->ew == ew)
{
lcc_edge *e = cir->missingE;
x->tag_coverCir(NULL);
lccCirAllocator.deallocate(cir);
lccEAllocator.deallocate(e);
return true;
}
if (!y->rc && x->prevE->ew == ew)
{
lcc_edge *e = x->prevE;
lccEAllocator.deallocate(e);

if (cir)
{
if (cir->pEx)
{
cir->pEx->tag_rev();

cir->pEx->fa = y, y->rc = cir->pEx;
y->nextE = cir->pEx->msg.firstE;
x->prevE = cir->pEx->msg.lastE;
}
else
y->nextE = x->prevE = cir->missingE;

y->update(), x->update();
x->tag_coverCir(NULL);

lccCirAllocator.deallocate(cir);
}
else
{
y->fa = NULL, y->nextE = NULL, y->update();
x->lc = NULL, x->prevE = NULL, x->update();
}

return true;
}
return false;
}
bool cactus_add(int qv, int qu, int delta)
{
lcc_node *x = lccVer + qv, *y = lccVer + qu;
if (x->findRoot() != y->findRoot())
return false;

x->makeRoot(), y->access();
if (y->msg.hasMultiplePath)
return false;
y->tag_addWB(delta);
return true;
}
path_message cactus_query(int qv, int qu)
{
path_message res;
lcc_node *x = lccVer + qv, *y = lccVer + qu;
if (x->findRoot() != y->findRoot())
{
res.setInvalid();
return res;
}

x->makeRoot(), y->access();
res = y->msg.pathMsg;
if (y->msg.hasMultiplePath)
res.setMultiple();
return res;
}

int main()
{
int nQ;

cin >> n >> nQ;

cactus_init();
while (nQ--)
{
char type;
while (type = getchar(), type != 'l' && type != 'c' && type != 'a' && type != 'd');

if (type == 'l')
{
int v = getint(), u = getint(), wA = getint(), wB = getint();

if (cactus_link(v, u, wA, wB))
printf("ok\n");
else
printf("failed\n");
}
else if (type == 'c')
{
int v = getint(), u = getint(), wA = getint(), wB = getint();

if (cactus_cut(v, u, wA, wB))
printf("ok\n");
else
printf("failed\n");
}
else if (type == 'a')
{
int v = getint(), u = getint(), delta = getint();
if (cactus_add(v, u, delta))
printf("ok\n");
else
printf("failed\n");
}
else if (type == 'd')
{
int v = getint(), u = getint();

path_message ret = cactus_query(v, u);
printf("%d %d\n", ret.minLA, ret.minWB);
}
else
{
puts("error!");
}
}

return 0;
}


  评论这张
 
阅读(7967)| 评论(9)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017