Tối ưu hóa xây dựng đồ thị bằng cấu trúc dữ liệu

Trong một số trường hợp, chúng ta cần nối tất cả các đỉnh có chỉ số trong đoạn [L, R] với tất cả các đỉnh có chỉ số trong đoạn [L', R']. Nếu thực hiện trực tiếp sẽ dẫn đến độ phức tạp O(n²m). Do đó, chúng ta cần phân chia đoạn thành các khối nhỏ để xử lý thống nhất.

Chúng ta cần xây dựng một cây vào và một cây ra. Các đỉnh trong cây vào biểu diễn cho các cạnh có thể kết nối đến bất kỳ điểm nào trong đoạn; các đỉnh trong cây ra biểu diễn cho việc tất cả các điểm trong đoạn đều có thể tạo cạnh ra ngoài.

Đầu tiên, chúng ta xử lý các liên kết giữa các khối:

• Tất cả các nút cha trong cây vào nối đến con của nó với trọng số 0 (nếu có thể đến đoạn [1, 10], thì chắc chắn có thể đến [1, 5] và [6, 10]);
• Tất cả các nút con trong cây ra nối đến cha của nó với trọng số 0 (nếu có thể xuất phát từ một số điểm trong [1, 5], thì cũng có thể xuất phát từ một số điểm trong [1, 10]);
• Tất cả các nút trong cây vào nối đến nút tương ứng trong cây ra với trọng số 0 (nếu có thể đến tất cả các điểm trong [1, 10], thì chắc chắn có thể xuất phát từ một số điểm trong [1, 10]).

(Nói ngắn gọn, cây vào là cây hướng ra ngoài, cây ra là cây hướng vào trong, các cây nối với nhau)

Khi cần nối đoạn [l, r] → [l', r'], chúng ta chia đoạn [l, r] trong cây ra thành nhiều đoạn nhỏ, nối đến một nút trung gian pᵢ, sau đó nối pᵢ đến các đoạn nhỏ trong [l',r'] của cây vào.

Cuối cùng, xử lý toàn bộ như một đồ thị bình thường. Đảm bảo thông tin tại các nút lá cuối cùng là chính xác. (Tất cả các thao tác bắt đầu từ các nút vào)

Vì các nút trong cây vào đều nối đến các nút tương ứng trong cây ra bằng các cạnh không quan trọng, khiến thông tin trong cây ra cuối cùng bị cập nhật bởi thông tin trong cây vào, nhưng không đảm bảo thông tin trong cây vào bị cập nhật bởi thông tin trong cây ra. Do đó, chúng ta chỉ cần bắt đầu từ cây vào để đảm bảo thông tin của hai cây cuối cùng nhất quán.

Bài tập ví dụ: CF786B Legacy

Nội dung: Hỗ trợ nối một điểm đến nhiều điểm, tìm đường đi ngắn nhất từ một nguồn.

Bài toán mẫu. Chỉ cần tìm nút s trong cây vào rồi chạy thuật toán tìm đường đi ngắn nhất. Cuối cùng, thông tin trong các nút lá của cả hai cây đều đúng.

Bài tập ví dụ: P3588 [POI2015]PUS

Nội dung: Biết trước một phần các giá trị trong dãy, biết rằng giá trị nhỏ nhất trong một số đoạn phải lớn hơn tất cả các giá trị còn lại. Yêu cầu kiểm tra khả năng tồn tại hoặc xây dựng dãy.

Ràng buộc hiệu + tối ưu hóa xây dựng đồ thị bằng cây đoạn.

Một số kỹ thuật nhỏ giúp giảm độ phức tạp lập trình:

• Có thể viết riêng phần xây dựng cây vào và cây ra, ghi nhớ số lượng nút của một cây tot, sau đó nối các cạnh giữa hai cây bằng cách (cur - tot) → cur.
• Khi xây dựng cây, có thể lưu lại số hiệu của nút lá tương ứng với mỗi vị trí, thuận tiện cho truy vấn điểm đơn.

void construct_in_tree(int left, int right, int &current) {
    current = ++total_nodes;
    if (left == right) 
        return leaf_in[left] = current, values[current] = input_array[left], void();
    
    int mid = (left + right) >> 1;
    construct_in_tree(left, mid, left_child[current]);
    construct_in_tree(mid + 1, right, right_child[current]);
    add_edge(current, left_child[current], 0); 
    add_edge(current, right_child[current], 0);
}

void construct_out_tree(int left, int right, int &current) {
    current = ++total_nodes;
    add_edge(current - tree_count, current, 0);
    if (left == right) 
        return leaf_out[left] = current, values[current] = input_array[left], void();
    
    int mid = (left + right) >> 1;
    construct_out_tree(left, mid, left_child[current]);
    construct_out_tree(mid + 1, right, right_child[current]);
    add_edge(left_child[current], current, 0);
    add_edge(right_child[current], current, 0);
}

P5025 [SNOI2017]Bombs

Nội dung: Tính số lượng quả bom bị kích nổ trên trục tọa độ một chiều

Thực chất yêu cầu đếm tổng trọng số các đỉnh có thể đến được từ một điểm trong đồ thị có hướng.

Cần nối điểm đơn đến đoạn điểm. Do đó cần tối ưu hóa xây dựng đồ thị bằng cây đoạn.

Thu hẹp đồ thị rồi chạy DP Cách này sẽ bị tính trùng, nhưngdo dữ liệu trên Luogu quá yếu, trên BZOJ có thể AC, trên Luogu đạt 86 điểm

Vì kết quả cuối cùng chắc chắn là một đoạn liên tục, nên có thể ghi nhận mx và mn, sau đó DFS với memoization.

Sau đó chỉ còn được 56 điểm

Dường như xây hai cây ở đây sẽ bị sai, có vẻ trong một số trường hợp chỉ nên xây một cây. (Chỉ khi có cạnh từ điểm đơn đến nhiều điểm)

Jump

Bài này khá đặc biệt. Bài toán tận dụng ưu điểm về tiêu thụ bộ nhớ thấp của K-D Tree để thực hiện tối ưu hóa xây dựng đồ thị cho bài toán đường đi ngắn nhất từ điểm đơn đến hình chữ nhật.

Điều này cũng gợi ý rằng chúng ta có thể linh hoạt sử dụng các cấu trúc dữ liệu khác nhau để tối ưu hóa xây dựng đồ thị. Miễn là phương pháp hợp lệ và bao gồm tất cả các trường hợp hợp lệ, đều có thể xem xét áp dụng.

Ants

Đây là bài sử dụng cây đoạn tối ưu hóa xây dựng đồ thị để giải bài toán 2-SAT, cần sử dụng tư tưởng tối ưu hóa tiền tố trong xây dựng đồ thị 2-SAT.

Tối ưu hóa tiền tố trong xây dựng đồ thị thường giải quyết vấn đề: nếu chọn một điểm trong tập hợp, thì các điểm còn lại không thể được chọn. Nó trông đại khái như thế này:

Hai hàng điểm đỏ là các điểm phụ trợ, lần lượt biểu diễn các điểm hậu tố và tiền tố. Các điểm hình vuông màu đen và nâu là các nút gốc.

Vấn đề của tối ưu hóa xây dựng đồ thị bằng cây đoạn là: một nút chứa nhiều điểm, nếu chọn một điểm, thì các điểm còn lại không thể được chọn, đồng thời các điểm trong nút tổ tiên và nút con cũng không thể được chọn. Nó đại khái như thế này:

Cơ bản là nối chuỗi các mối quan hệ cha con.

Cần lưu ý rằng phương pháp này có rất nhiều nút, cả số đỉnh và số cạnh đều ở mức O(n log n). Bài này sử dụng Heavy-Light Decomposition kết hợp với cây đoạn, nên là O(n log² n).

Flags

Đây là bài 2-sat sử dụng cây đoạn tối ưu hóa xây dựng đồ thị thông thường, các điểm và cạnh mới tạo không có tính đối xứng, chỉ tương đương với xây dựng đồ thị cơ bản.

Phụ lục

Mẫu: Đường đi ngắn nhất từ một nguồn (dùng để debug)

void construct_tree(int left, int right, int &current) {
    current = ++total_nodes;
    if (left == right) return ;
    
    int mid = (left + right) >> 1;
    construct_tree(left, mid, left_child[current]);
    construct_tree(mid + 1, right, right_child[current]);
    
    if (direction_type) {
        add_edge(current, left_child[current], 0);
        add_edge(current, right_child[current], 0);
    } else {
        add_edge(left_child[current], current, 0);
        add_edge(right_child[current], current, 0);
    }
}

int point_counter;
void process_outgoing(int left, int right, int l, int r, int parent, int weight, int current) {
    if (l <= left && right <= r) {
        add_edge(current, parent, 0);
        return ;
    }
    int mid = (left + right) >> 1;
    if (l <= mid) process_outgoing(left, mid, l, r, parent, weight, left_child[current]);
    if (r > mid) process_outgoing(mid + 1, right, l, r, parent, weight, right_child[current]);
}

void process_incoming(int left, int right, int l, int r, int parent, int weight, int current) {
    if (l <= left && right <= r) {
        add_edge(parent, current, weight);
        return ;
    }
    int mid = (left + right) >> 1;
    if (l <= mid) process_incoming(left, mid, l, r, parent, weight, left_child[current]);
    if (r > mid) process_incoming(mid + 1, right, l, r, parent, weight, right_child[current]);
}

inline void connect_range(int l, int r, int l_prime, int r_prime, int weight) {
    ++point_counter;
    process_outgoing(1, n, l, r, point_counter, weight, root_out);
    process_incoming(1, n, l_prime, r_prime, point_counter, weight, root_in);
}

int locate_leaf(int left, int right, int position, int current) {
    if (left == right) return current;
    int mid = (left + right) >> 1;
    if (position <= mid) return locate_leaf(left, mid, position, left_child[current]);
    return locate_leaf(mid + 1, right, position, right_child[current]);
}

struct Node {
    int node_id;
    long long distance;
    bool operator<(const Node &other) const {
        return distance > other.distance;
    }
};
priority_queue<Node> pq;

long long distances[MAX_NODES];
bool visited[MAX_NODES];

inline void dijkstra_algorithm() {
    int start_node = locate_leaf(1, n, source, root_in);
    memset(distances, 0x3f, sizeof(distances));
    
    pq.push({start_node, 0}); 
    distances[start_node] = 0;
    
    while (!pq.empty()) {
        int current = pq.top().node_id; 
        pq.pop();
        
        if (visited[current]) continue;
        visited[current] = true;
        
        for (int edge_idx = head[current]; edge_idx; edge_idx = edges[edge_idx].next) {
            int target = edges[edge_idx].target;
            if (distances[target] > distances[current] + edges[edge_idx].weight) {
                distances[target] = distances[current] + edges[edge_idx].weight;
                pq.push({target, distances[target]});
            }
        }
    }
}

void print_result(int left, int right, int current) {
    if (left == right) {
        printf("%lld ", distances[current] >= INF ? -1ll : distances[current]);
        return ;
    }
    int mid = (left + right) >> 1;
    print_result(left, mid, left_child[current]);
    print_result(mid + 1, right, right_child[current]);
}

int main() {
    scanf("%d %d %d", &n, &m, &source);
    direction_type = 1; 
    construct_tree(1, n, root_in); 
    int temp_total = total_nodes;
    
    direction_type = 0; 
    construct_tree(1, n, root_out);
    
    for (int i = 1; i <= temp_total; ++i)
        add_edge(i, i + temp_total, 0);
    
    point_counter = total_nodes;
    
    // Xử lý các yêu cầu nối
    for (...) connect_range(l, r, l_prime, r_prime);
    
    dijkstra_algorithm();
    print_result(1, n, root_in);
    puts("");
    return 0;
}