Thư viện tài liệu, ebook tham khảo dành cho học sinh, sinh viên

cố định thành phố xuất phát là 71. Bài toán Ngưòi du lịch được đưa về bài toán: Tìm cực tiêu của hàm f(x2,x3,.,xn) = c[l,x2] + c[x2,x3] + . + c[x„_i,x„] + c[xn,Xi] -> min Gọi: Cmin = min {c[7, j], i,j = l,2,.,n,i / j} là chi phí đi lại nhỏ nhất giữa các thành phố. Giả sử ta đang có phương án bộ phận (ưi, Ư2. Uk) tương ứng vói hành trình bộ phậ...

32 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 706 | Lượt tải: 0

Có nhiều dạng đồ thị: ► Có hướng vs. Vô hướng ► Có trọng số vs. Không trọng số ► Dơn đồ thị vs. Đa đồ thị Có nhiều cách biểu diễn đồ thị Một số đồ thị đặc biệt (như Cây) có cách biểu diễn đặc biệt Chủ yếu sử dụng các biểu diễn chung: o Danh sách kề Ỡ Ma trận kề Ỡ Danh sách cạnh

45 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 568 | Lượt tải: 0

Bài toán: Gõ SMS Dữ liệu vào Dòng đầu tiên là một số nguyên T là số lượng bộ test. T dòng tiếp theo mỗi dòng chỉ chứa các khoảng trống và các ký tự in thường. Mỗi dòng chứa ít nhất 1 và tối đa 100 ký tự. Kết quả ra Mỗi test đầu vào tưong ứng với một dòng ỏ kết quả ra. Mỗi dòng bắt đầu bởi thứ tự test và sau đó là một số biểu thị số lần bấm phím...

46 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 653 | Lượt tải: 0

Exercises BOUNDED-MST void solve(){ ans = INF; X[0] = 0; TRY(1); cout << ans; } int main(){ input(); solve(); }Exercises MaxClique  Cho đồ thị vô hướng G=(V,E). Một đồ thị G’=(V’, E’) được gọi là đồ thị con của G nếu V’ là tập con của V và E’ là tập con của E. Hãy tìm đồ thị con của G là đồ thị đầy đủ và có số đỉnh lớn nhất Exerci...

141 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 578 | Lượt tải: 0

Sample code #include using namespace std; const int N = 10000; int n,m; vector A[N]; bool visited[N]; int num[N]; int low[N]; int t; vector<> > bridges; void input(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= m; i++){ int u,v; cin >> u >> v; A[u].push_back(v); A[v...

21 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 628 | Lượt tải: 0

Bài toán Range Minimum Query RMQ preprocessing(){ for (i = 0; i < N; i++) M[0,i] = i; for (j = 0; 2j ≤ N; j++){ for(i = 0; i + 2j -1 < N; i++){ if a[M[j-1,i]] < a[M[j-1,i+2j-1]] then{ M[j,i] = M[j-1,i]; }else{ M[j,i] = M[j-1,i+2j-1];  Truy vấn RMQ(i,j)  k = [log(j-i+1)]  RMQ(i,j) = M[k,i] nếu a[M[k,i]] ≤ a[M[k, j-2k+1]] M[k, j-2k+1]...

6 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 762 | Lượt tải: 0

Quy hoạch động sử dụng deque  Định nghĩa bài toán con  S(i): tổng cực đại của dãy con của dãy a1, , ai thỏa mãn đề bài mà phần tử cuối cùng là ai  Công thức quy hoạch động  S(i) = max(ai + S(j) | L1 ≤ i – j ≤ L2}  Khởi tạo deque, lưu trữ các chỉ số j sao cho S(j) không tăng và là ứng cử viên để tính toán các bài toán con S(i)  Mỗi khi...

6 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 544 | Lượt tải: 0

Truy vết  Bài toán dãy con tăng dần dài nhất  prev[i]: chỉ số của phần tử trước phần tử a[i] trong lời giải của bài toán con Pi.  select: chỉ số của bài toán con mà lời giải của bài toán con đó là lời giải của bài toán xuất phát 16Truy vết incsubseq(a1,a2,. . ., aN){ s[1] = 1; prev[1] = -1; res = s[1]; select = 1; for i = 2 → N do{ s[...

20 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 618 | Lượt tải: 0

Giảm để trị  Chia bài toán (chia theo dữ liệu) xuất phát thành các bài toán con  Giải 1 bài toán con và dẫn ra lời giải của bài toán xuất phát (các bài toán con khác không cần giải  tránh dư thừa)  Tìm kiếm nhị phân  Tính lũy thừa Tìm kiếm nhị phân Mã giả bSearch(a,left, right, x){ if left = right then{ if a[left] = x return left; ...

31 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 716 | Lượt tải: 0

huật toán nhánh và cận 64  Duyệt nhánh và cận:  Phương án bộ phận (a1, , ak) trong đó a1 gán cho x1, ak gán cho xk  Phương án (a1, , ak, bk+1, ,bn) là một phương án đầy đủ được phát triển từ (a1, ,ak) trong đó bk+1 gán cho xk+1, , bn được gán cho x n  Với mỗi phương án bộ phận (x1, , xk), hàm cận dưới g(x1, , xk ) có giá trị khôn...

66 trang | Chia sẻ: hachi492 | Ngày: 06/01/2022 | Lượt xem: 634 | Lượt tải: 0