Đường đi ngắn nhất. Thuật toán Dijkstra's với priority_queue hay set trong

Thuật toán Dijkstra 

Độ phức tạp: O(E.logV)

#include <bits/stdc++.h>
using namespace std;

const int INT_MAX = 1e9;
typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> dist, pre;
Thuật toán Dijkstra với priority_queue

void Dijkstra(int s) {
  // Khoi tao
  int n = adj.size();
  dist.assign(n, INT_MAX);
  dist[s] = 0;
  pre.assign(n, -1);

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, s));

  // Lap
  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();

    if (d != dist[u]) continue;

    for (int i=0; i<(int) adj[u].size(); i++) {
      int v = adj[u][i].first;
      int uv = adj[u][i].second;
      

      if (dist[v] > d+uv) {
        dist[v] = d+uv;
        pre[v] = u;
        q.push(make_pair(dist[v], v));      
      }
    }
  }
}



Thuật toán Dijkstra với set

void Dijkstra2(int s) {
  // Khoi tao  
  int n = adj.size();  
  dist.assign(n, INT_MAX);  
  dist[s] = 0;  
  pre.assign(n, -1);  

  set<pii> q;  
  q.insert(make_pair(0, s));  

  // Lap  
  while (!q.empty()) {    
    int u = q.begin()->second;

    q.erase(q.begin()); 
   
    for (int i=0; i<(int) adj[u].size(); i++) {      
      int v = adj[u][i].first;      
      int uv = adj[u][i].second;     

      if (dist[v] > dist[u]+uv) {        
        q.erase(make_pair(dist[v], v));        
        dist[v] = ndist[u]+uv;        
        pre[v] = u;        
        q.insert(make_pair(dist[v], v));      
      }    
    }
  }
}


int main() {
  adj.resize(2);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(2, -5));
  adj[0].push_back(make_pair(2, 8));

  Dijkstra(0);

  for (int i = 0; i < dist.size(); i++)  cout << dist[i] << endl;
}

CTDL Disjoint-set với rank heuristic

CẤU TRÚC DỮ LIỆU DISJOIN - SET

Ý nghĩa: cấu trúc dữ liệu Disjoin - set dùng để biểu diễn các tập hợp, mỗi tập hợp có thể có giá trị từ 0 đến n. Disjoin - set cho phép thực hiện nhanh các thao tác như: 
(1) Hợp 2 tập hợp thành một tập hợp
(2) Kiểm tra 2 phần tử có thuộc tập hợp không

Cấu trúc dữ liệu:

• Các phần tử: có giá trị từ 0, 1, 2, ..., n
• Các phần tử này thuộc tập hợp nào đó, nên ta quản lý tập hợp phần tử i thuộc là parent[i]. Như vậy một tập hợp là một cái cây, và gốc của cây là giá trị đại diện cho tập hợp

Như vậy, cấu disjoin set chỉ đơn giảng là một mảng parent[] của các phần tử i cho biết cha của phần tử i là ai.


Chương trình:
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000;

// Cấu trúc dữ liệu
int parent[maxn];
int n;

int rank[maxn];


void Init(int num) {
  n = num;
  fill(rank, rank + n, 0);
  for (int i = 0; i < n; i++) parent[i] = i;
}


int Root(int x) {
  return (x == parent[x]) ? x : (parent[x] = Root(parent[x]));
}


void UnionSet(int a, int b) {
  a = Root(a);
  b = Root(b);
  if (a == b) return;
  if (rank[a] < rank[b]) swap(a, b);
  if (rank[a] == rank[b]) ++rank[a];
  parent[b] = a;
}

bool IsSameSet(int a, int b) {
  a = Root(a);
  b = Root(b);

  return a==b;
}

int main() {
  Init(3);
  UnionSet(0, 2);
  cout << (0 == Root(0)) << '\n';
  cout << (1 == Root(1)) << '\n';
  cout << (0 == Root(2)) << '\n';
}

Fenwick tree

Fenwick tree

Bài toán
Cho dãy số a=(a(1), a(2), ..., a(n)) và nhiều phép truy vấn Sum(l, r) dùng tính tổng dãy con a(l) + a(l+1) + ... + a(r) và truy vấn Update(i, x) để tăng giá trị a(i) lên x giá trị.

Giải pháp Fenwick tree
Giới thiệu:

1. Fenwick tree hay Binary Indexed Tree (BIT) là phương pháp tiền xử lý giúp tính tổng Sum(l, r) và cập nhật Update(i, x) trên dãy số a trong thời gian O(log n). 
2. Lịch sử: Phương pháp Fenwick tree do Pete Fenwickin đề xuất vào năm 1994.
3. Độ phức tạp: Độ phức tạp của phép toán tính tổng dãy con và cập nhật các phần tử của mảng là O(log n)

Ý tưởng Fenwick tree:
Fenwick tree là mảng T[1...n], trong T[i] = tổng các phần tử dãy a thuộc đoạn [(i-2^k)+1, i], trong đó k là vị trí bit 1 nằm bên phải nhất của số nhị phân của biến i.

Bây giờ, chúng ta sẽ trình bày toàn bộ code của Fenwick tree:

void Update(int i, int x) {
    while (i<n) {
        T[i] += x;
        i |= (i + 1);
    }
}

int Sum(int n) {
    int res = 0;
    while (n>= 0) {
        res += data[n];
        n= (n& (n+1)) - 1;
    }
    return res;
}

Ở đây, Sum(i) trả về tổng của các phần tự từ phần tử đầu tiên đến phần tử thứ i. Việc tìm tổng của một đoạn bất kỳ có thể thực hiện bằng truy vấn Sum(right)-Sum(left-1). 

Fenwick tree chuẩn chỉ hỗ trợ cập nhật 1 phần tử tại một thời điểm. Tuy nhiên, chúng ta có thể mở rộng cho việc cập nhật cả một đoạn - câu lệnh cập nhật sẽ phát biểu thành "tăng mỗi giá trị giữa left và right một lượng giá trị". Chúng ta có thể chỉnh sửa cây cho cập nhật như thế trong thời gian O(log n):

void Update(int left, int right, int by) {
    internalUpdate(left, by, -by * (left - 1));
    internalUpdate(right, -by, by * right);
}

void InternalUpdate(int i, int mul, int add) {
    while (i<n) {
        dataMul[i] += mul;
        dataAdd[i] += add;
        i|=(i+ 1);
    }
}

int Query(int i) {
    int mul = 0;
    int add = 0;
    int start = i;
    while (i>= 0) {
        mul += dataMul[i];
        add += dataAdd[i];
        i= (i& (i+ 1)) - 1;
    }
    return mul * start + add;
}