天天看點
傳回

【bzoj2049】[Sdoi2008]Cave 洞穴勘測——線段樹上bfs求可撤銷并查集題面分析AC code

題面

2049: [Sdoi2008]Cave 洞穴勘測

Time Limit: 10 Sec Memory Limit: 259 MB

Submit: 12030 Solved: 6024

Description

輝輝熱衷于洞穴勘測。某天，他按照地圖來到了一片被标記為JSZX的洞穴群地區。經過初步勘測，輝輝發現這片區域由n個洞穴（分别編号為1到n）以及若幹通道組成，并且每條通道連接配接了恰好兩個洞穴。假如兩個洞穴可以通過一條或者多條通道按一定順序連接配接起來，那麼這兩個洞穴就是連通的，按順序連接配接在一起的這些通道則被稱之為這兩個洞穴之間的一條路徑。洞穴都十分堅固無法破壞，然而通道不太穩定，時常因為外界影響而發生改變，比如，根據有關儀器的監測結果，123号洞穴和127号洞穴之間有時會出現一條通道，有時這條通道又會因為某種稀奇古怪的原因被毀。輝輝有一台監測儀器可以實時将通道的每一次改變狀況在輝輝手邊的終端機上顯示：如果監測到洞穴u和洞穴v之間出現了一條通道，終端機上會顯示一條指令 Connect u v 如果監測到洞穴u和洞穴v之間的通道被毀，終端機上會顯示一條指令 Destroy u v 經過長期的艱苦卓絕的手工推算，輝輝發現一個奇怪的現象：無論通道怎麼改變，任意時刻任意兩個洞穴之間至多隻有一條路徑。因而，輝輝堅信這是由于某種本質規律的支配導緻的。因而，輝輝更加夜以繼日地堅守在終端機之前，試圖通過通道的改變情況來研究這條本質規律。然而，終于有一天，輝輝在堆積成山的演算紙中崩潰了……他把終端機往地面一砸（終端機也足夠堅固無法破壞），轉而求助于你，說道：“你老兄把這程式寫寫吧”。輝輝希望能随時通過終端機發出指令 Query u v，向監測儀詢問此時洞穴u和洞穴v是否連通。現在你要為他編寫程式回答每一次詢問。已知在第一條指令顯示之前，JSZX洞穴群中沒有任何通道存在。

Input

第一行為兩個正整數n和m，分别表示洞穴的個數和終端機上出現過的指令的個數。以下m行，依次表示終端機上出現的各條指令。每行開頭是一個表示指令種類的字元串s（"Connect”、”Destroy”或者”Query”，區分大小寫），之後有兩個整數u和v (1≤u, v≤n且u≠v) 分别表示兩個洞穴的編号。

Output

對每個Query指令，輸出洞穴u和洞穴v是否互相連通：是輸出”Yes”，否則輸出”No”。（不含雙引号）

Sample Input

樣例輸入1 cave.in

200 5

Query 123 127

Connect 123 127

Query 123 127

Destroy 127 123

Query 123 127

樣例輸入2 cave.in

3 5

Connect 1 2

Connect 3 1

Query 2 3

Destroy 1 3

Query 2 3

Sample Output

樣例輸出1 cave.out

No

Yes

No

樣例輸出2 cave.out

Yes

No

HINT

資料說明 10%的資料滿足n≤1000, m≤20000 20%的資料滿足n≤2000, m≤40000 30%的資料滿足n≤3000, m≤60000 40%的資料滿足n≤4000, m≤80000 50%的資料滿足n≤5000, m≤100000 60%的資料滿足n≤6000, m≤120000 70%的資料滿足n≤7000, m≤140000 80%的資料滿足n≤8000, m≤160000 90%的資料滿足n≤9000, m≤180000 100%的資料滿足n≤10000, m≤200000 保證所有Destroy指令将摧毀的是一條存在的通道本題輸入、輸出規模比較大，建議c\c++選手使用scanf和printf進行I\O操作以免逾時

分析

一條邊的存在的時間其實就是一段連續的時間（我們這裡指定每一行指令就是一個機關的時間），這樣我們就可以把問題離線化。

那麼我們可以用線段樹來儲存整個狀态，這并不是什麼難事，我們線上段樹的每一個節點上儲存一個邊的集合，表示這個節點下所有的子節點都包含了這條邊。

那麼我們對于任意一個葉子節點，從根節點到葉子節點的全過程周遊到的所有的邊組成的集合就是目前的圖

由于如果每次詢問都是從根節點出發的話效率太低，我們采用直接線上段樹上移動的方式來解決效率問題。

通過可撤銷并查集的性質，來實作線上段樹上移動

AC code 

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 10100;
const int MAXM = 200100;
 
typedef pair<int, int> pii;
 
struct UFS {
    int f[MAXN];
    stack<pii> s;
 
    int finds(int x) {
        while (x ^ f[x])
            x = f[x];
        return x;
    }
 
    void unite(int x, int y) {
        x = finds(x);
        y = finds(y);
        if (x != y) {
            s.push({x, f[x]});
            f[x] = y;
        }
    }
 
    void init(int b, int e) { // 初始化函數，範圍為 [b, e)
        for (int i = b; i < e; i++)
            f[i] = i;
    }
 
    void undo() {
        f[s.top().first] = s.top().second;
        s.pop();
    }
};
 
struct SegTree {
    vector<pii> data[MAXM << 2];
 
    static inline int lson(int k) { return k << 1; }
 
    static inline int rson(int k) { return (k << 1) | 1; }
 
    static inline int fat(int l, int r) { return (l + r) >> 1; }
    // add 函數對應于正常的線段樹的 insert，但是稍微有些不同
    void add(int k, int l, int r, int x, int y, const pii &value) {
        if (l == x && r == y) {
            data[k].push_back(value);
            return;
        }
        int mid = fat(l, r);
        if (y <= mid) {
            add(lson(k), l, mid, x, y, value);
        } else if (x > mid) {
            add(rson(k), mid + 1, r, x, y, value);
        } else {
            add(lson(k), l, mid, x, mid, value);
            add(rson(k), mid + 1, r, mid + 1, y, value);
        }
    }
};
 
UFS ufs;
SegTree segTree;
vector<pair<pii, int> > que;
int tar;
// 通過 dfs 的方式線上段樹上移動
bool dfs(int k, int l, int r) {
    // 當完成一次詢問之後，需要跳出目前的葉子，即回溯。通過 goto 來使得回溯的過程會自動進入正确的葉子節點
    rejudge:
    int target = que[tar].second;
    if (target == r && l == r) {
        if (ufs.finds(que[tar].first.first) == ufs.finds(que[tar].first.second))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        tar++;
        return tar == que.size();// true 表示所有的詢問已經結束，退出 dfs
    }
    int mid = SegTree::fat(l, r);
    if (target <= mid) {
//        for (auto &item: segTree.data[SegTree::lson(k)])
//            ufs.unite(item.first, item.second);
        for (int i = 0; i < segTree.data[SegTree::lson(k)].size(); ++i)
            ufs.unite(segTree.data[SegTree::lson(k)][i].first, segTree.data[SegTree::lson(k)][i].second);
        if (dfs(SegTree::lson(k), l, mid))
            return true;
//        for (auto &item: segTree.data[SegTree::lson(k)])
        for (int i = 0; i < segTree.data[SegTree::lson(k)].size(); ++i)
            ufs.undo();
        if (que[tar].second > r)
            return false;
        goto rejudge;
    } else {
//        for (auto &item: segTree.data[SegTree::rson(k)])
//            ufs.unite(item.first, item.second);
        for (int i = 0; i < segTree.data[SegTree::rson(k)].size(); ++i)
            ufs.unite(segTree.data[SegTree::rson(k)][i].first, segTree.data[SegTree::rson(k)][i].second);
        if (dfs(SegTree::rson(k), mid + 1, r))
            return true;
//        for (auto &item: segTree.data[SegTree::rson(k)])
        for (int i = 0; i < segTree.data[SegTree::rson(k)].size(); ++i)
            ufs.undo();
        if (que[tar].second > r)
            return false;
        goto rejudge;
    }
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    map<pii, int> mp;
    for (int i = 0; i < m; ++i) {
        string s;
        int u, v;
        cin >> s >> u >> v;
        if (u > v) swap(u, v);
        switch (s[0]) {
            case 'Q':
//                que.push_back({{u, v}, i + 1});
                que.push_back(make_pair(make_pair(u, v), i + 1));
                break;
            case 'C':
//                mp.insert({{u, v}, i + 1});
                mp.insert(make_pair(make_pair(u, v), i + 1));
                break;
            case 'D': {
//                auto iter = mp.find({u, v});
                map<pii, int>::iterator iter = mp.find(make_pair(u, v));
//                segTree.add(1, 1, m, iter->second, i, {u, v});
                segTree.add(1, 1, m, iter->second, i, make_pair(u, v));
                mp.erase(iter);
                break;
            }
        }
    }
    map<pii, int>::iterator iter = mp.begin();
    while (iter != mp.end()) {
        segTree.add(1, 1, m, iter->second, m, iter->first);
        iter++;
    }
    ufs.init(0, n + 1);
    tar = 0;
//    for (auto &item: segTree.data[1])
    for (int i = 0; i < segTree.data[1].size(); ++i)
        ufs.unite(segTree.data[1][i].first, segTree.data[1][i].second);
//        ufs.unite(item.first, item.second);
    dfs(1, 1, m);
    return;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    cin.tie(nullptr);
//    cout.tie(nullptr);
#ifdef ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    long long test_index_for_debug = 1;
    char acm_local_for_debug;
    while (cin >> acm_local_for_debug) {
        if (acm_local_for_debug == '$') exit(0);
        cin.putback(acm_local_for_debug);
        if (test_index_for_debug > 20) {
            throw runtime_error("Check the stdin!!!");
        }
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    }
#else
    solve();
#endif
    return 0;
}
ACM # 資料結構 dfs 程式設計
上一篇: Compiere 工作流引擎
下一篇: apache 工作流引擎_SpringBoot開發案例之整合Activiti工作流引擎

繼續閱讀