2015-08-09

b483. 史蒂芙的觀察日記

1. Problem
1. 1.1. 背景
2. 1.2. 題目描述
2. Sample Input
3. Sample Output
4. Solution
1. 4.1. 小記

Problem

背景

史蒂芙在學院讀書時，教授曾經教過最小生成樹 (Minimum Spanning Tree，簡稱 MST)，MST 最常見到的兩個算法 Kruskal’s Algorithm、Prim’s Algorithm，還有其他的算法來得到 MST。

在某一次作業中，史蒂芙被特別指派的某一道題目，題目描述「給定好一棵 MST，接著新增加一條邊，請問新的最小生成樹成本為何。」聰明的史蒂芙想到一個樸素的解法「增加新的一條邊若造成 MST 上存在一個環，只要把環上最權重最大的邊移除，最小生成樹就大功告成。」

萬萬沒想到，正高興地要拿著 $O(V)$ 算法交差時，卻沒想到一連串的詢問，於是史蒂芙被命令回去觀察觀察一番再交出報告。「看來史蒂芙還是只有被欺負的份呢。」

題目描述

給定 $N$ 個點、$M$ 條雙向邊，依序給定每一條邊，每增加一條邊，輸出當前的最小生成樹成本，若圖不連通，則輸出最小生成森林成本。

Sample Input

Sample Output

Case #1
1
3
3
Case #2
9
17
24
30
27
22
19

Solution

用 Link/Cut tree 解 MST 相當瘋狂的舉動，可以將找環上最重邊移除的操作降到 $O(\log V)$。最小生成樹是一個無向的樹，而邊的權重可以轉化成一個點，例如 ei(x, y, v) 相當於 x <-> ei <-> y 其中節點 x, y 帶有的權重為 0，而 ei 是一個虛設點帶權重為 v。

假設增加一條邊 ej(x, y, v) 會產生一個環，先檢查節點 x, y 是否在同一個集合內，若不在同一個集合直接建起這一條邊。反之，找到路徑 path(x, y) 上的點權最大值，接著映射回去，移除掉虛設點的兩個連接邊 x <-> ei 和 ei <-> y。

由於是一個無向樹，在尋找路徑時可以使用以下寫法 (否則要用另外一種，但這種寫法比較簡潔)

Node* maxPath(Node *x, Node *y) {
    mk_root(x);
    access(y), splay(y);
    return y->mxv;
}

如果 x 本身不是根，則這個操作會改變樹的上下層關係，對於有向樹會有差別，如 Node* find(Node *x) 中反映出來並非有向樹的唯一根，只能用來計算並查集的關係 find(x) == find(y)。

能不能減少虛設點的使用？
目前我沒辦法解決這問題，若要減少虛設點，則每個節點的權重代表維護到父節點的邊權重 (可以參考 UVa 11994 - Happy Painting)，仍然可以找到路徑上的最重邊，問題在於加入新的一條邊時，兩個有根樹要合併，由於其中一端可能不是其中一個的樹根，其上下層關係需要反轉，則邊權代表邊權的能力就會失效。也許可以利用標記傳遞來重新配置，寫起來恐怕會非常複雜。而虛設點會讓點數增加兩倍，耗時多兩倍是可以接受的方案。

小記

最近在撸 Link/Cut Tree (LCT)，於是拿去解決最小生成樹 MST，複雜度仍然是 $O(n \log n)$，甚至提供動態支持，儘管常數多了好幾倍，總算解決曾經在算法習題裡面的困惑。

當然想找個替代方案－塊狀樹之類的，但沒想到要支持一塊是樹，塊跟塊之間又串成樹，還要支持動態的合併跟分裂塊，為了找路徑，也許要在每一塊套倍增算法 … 代碼敲到一半，崩。

#include <bits/stdc++.h> 
using namespace std;
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 262144;
    struct Node {
        static Node *EMPTY;
        Node *ch[2], *fa;
        int rev;
        int val, size;
        Node *mxv;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            rev = 0;
            val = 0;
            mxv = this, size = 1;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
            if (rev) {
                ch[0]->rev ^= 1, ch[1]->rev ^= 1;
                swap(ch[0], ch[1]);
                rev ^= 1;
            }
        }
        void pushup() {
            if (this == EMPTY)	return ;
            mxv = this, size = 1;
            if (ch[0] != EMPTY) {
                if (ch[0]->mxv->val > mxv->val)	mxv = ch[0]->mxv;
                size += ch[0]->size;
            }
            if (ch[1] != EMPTY) { 
                if (ch[1]->mxv->val > mxv->val)	mxv = ch[1]->mxv;
                size += ch[1]->size;
            } 
        }
    } _mem[MAXN];
    
    int bufIdx;
    LCT() {
        Node::EMPTY = &_mem[0];
        Node::EMPTY->fa = Node::EMPTY->ch[0] = Node::EMPTY->ch[1] = Node::EMPTY;
        Node::EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        *u = Node();
        u->fa = u->ch[0] = u->ch[1] = Node::EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushup();
    }
    Node* access(Node *u) {
        Node *v = Node::EMPTY;
        for (; u != Node::EMPTY; u = u->fa) {
            splay(u);
            u->ch[1] = v;
            v = u;
            v->pushup();
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u)->rev ^= 1, splay(u);
    }
    void cut(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        y->ch[0] = x->fa = Node::EMPTY;
    }
    Node* _cut(Node *rt, Node *x) {
        Node *u, *v;
        mk_root(rt);
        access(x), splay(x);
        for (v = x->ch[0]; v->ch[1] != Node::EMPTY; v = v->ch[1]);
        x->ch[0]->fa = x->fa;
        x->fa = x->ch[0] = Node::EMPTY;
        return v;
    }
    void link(Node *x, Node *y) {
        mk_root(x);
        x->fa = y;
    }
    Node* find(Node *x) {
        for (x = access(x); x->pushdown(), x->ch[0] != Node::EMPTY; x = x->ch[0]);
        return x;
    }
    //
    Node* maxPath(Node *x, Node *y) {
        mk_root(x);
        access(y), splay(y);
        return y->mxv;
    }
    void debug(int n) {
    }
} tree;
LCT::Node *LCT::Node::EMPTY;
LCT::Node *A[262144];
int x[131072], y[131072];
int main() {
    int n, m, w, u, v, cmd;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2) {
        printf("Case #%d\n", ++cases);
        tree.init();
        for (int i = 1; i <= n; i++)
            A[i] = tree.newNode();
        
        int vcnt = n+1, mst = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d %d", &x[i], &y[i], &w);
            A[i+n] = tree.newNode();
            A[i+n]->val = w;
            if (tree.find(A[x[i]]) != tree.find(A[y[i]])) {
                tree.link(A[x[i]], A[i+n]);
                tree.link(A[y[i]], A[i+n]);
                mst += w;
            } else {
                LCT::Node *e = tree.maxPath(A[x[i]], A[y[i]]);
                if (e->val > w) {
                    mst += w - e->val;
                    int eid = e - tree._mem - n;
//					printf("eeeee %d %d %d\n", x[eid], y[eid], e->val);
                    tree.cut(A[x[eid]], e);
                    tree.cut(A[y[eid]], e);
                    tree.link(A[x[i]], A[i+n]);
                    tree.link(A[y[i]], A[i+n]);
                }
            }
            printf("%d\n", mst);
        }
    }
    return 0;
}
/*
3 3
1 2 1
1 3 2
2 3 4
*/

Morris' Blog