Chuyên đề Một Số Bài Tập ứng Dụng Của Tìm Kiếm ưu Tiên Theo Chiều ...

* Hướng dẫn thuật toán: - Sử dụng thuật toán Tajan để tìm các thành phần liên thông mạnh, tại mỗi thành phần liên thông mạnh sẽ xây dựng một đồn cảnh sát có chi phí xây dựng là nhỏ nhất,

MỘT SỐ BÀI TẬP ỨNG DỤNG CỦA TÌM KIẾM ƯU TIÊN THEO CHIỀU SÂU

(DFS) TRÊN ĐỒ THỊ

Depth first search (DFS) là một trong những thuật toán tìm kiếm kinh điển trên đồ thị Thuật toán không chỉ đơn thuần là duyệt tìm kiếm ưu tiên theo chiều sâu, mà ứng dụng của nó cũng rất sâu sắc trong việc tìm cây khung, tìm chu trình, tìm thành phần liên thông mạnh, tìm cầu và khớp, sắp xếp topo

Trong chuyên đề này, tôi không nhắc lại lý thuyết của DFS (vì đã có rất nhiều tài liệu viết

về vấn đề này rồi), mà ở đây tôi chỉ chú trọng vào những bài tập ứng dụng của DFS nhằm giúp người đọc có cái nhìn toàn diện về thuật toán này

Bài 1 Đường 1 chiều

Một hệ thống giao thông gồm có N nút giao thông đánh số từ 1 đến N và M đường hai chiều nối một số cặp nút, không có hai đường nối cùng một cặp nút Hệ thống đảm bảo

đi lại giữa hai hút bất kì Để đảm bảo an toàn, người ta quyết định rằng các đường hai chiều trước đây nay sẽ thành một chiều, và vấn đề ở chỗ chọn chiều cho mỗi đường như thế nào

Hãy tìm cách định hướng các cạnh sao cho hệ thống vẫn đảm bảo đi lại giữa hai cặp nút bất kì

INPUT: ONEWAY.INP

- Dòng đầu ghi hai số nguyên dương N, M (1 <= N <= 50000 , 1 <= M <= 100000)

- M dòng tiếp theo, mỗi dòng thể hiện một đường hai chiều gồm u, v là chỉ số hai nút

mà nó nối tới

OUTPUT: ONEWAY.OUT

- Dòng đầu ghi 1/0 tương ứng với có tìm được phương án thoả mãn hay không

- Nếu có, M dòng tiếp theo mỗi dòng thể hiện sự định hướng một cạnh bao gồm hai

số u, v với ý nghĩa định hướng cạnh (u,v) thành đường một chiều từ u đến v

- Sau khi định chiều xong ta được một đồ thị 1 chiều mới, kiểm tra đồ thị mới có liên thông không (sử dụng thuật toán Tajan) Nếu có thì trả lời có phương án, ngược lại thì không có phương án

vector <int> adj[nmax], adj1[nmax];

int dd[nmax], d[nmax], cha[nmax], num[nmax], low[nmax];

int n, m, id, dem=0;

else if (cha[u] == v) adj1[v].push_back(u);

else if (d[u] < d[v]) adj1[v].push_back(u); else adj1[u].push_back(v);

for (int u=1; u<=n; u++)

for (int i=0; i<adj1[u].size(); i++)

Một thành phố có N địa điểm chiến lược và M con đường một chiều giữa các địa điểm

Là thị trưởng của thành phố, bạn sẽ phải bảo vệ an toàn cho N địa điểm này

Để có thể bảo vệ cho các địa điểm, bạn phải xây dựng các đồn cảnh sát tại một vài địa điểm Đồn cảnh sát tại địa điểm i có thể bảo vệ cho địa điểm j nếu i = j hoặc cảnh sát có thể đi tuần tới địa điểm j từ i và có thể quay trở lại đồn tại địa điểm i

Để có thể xây dựng được các đồn cảnh sát cần phải mất chi phí, do địa hình mỗi địa điểm

là khác nhau nên chi phí xây dựng đồn cũng có thể khác nhau

Bạn phải xác định số tiền nhỏ nhất để xây dựng các đồn cảnh sát để có thể bảo vệ được tất cả N địa điểm, hơn nữa bạn phải đưa ra có bao nhiêu cách xây dựng để đảm bảo chi phí nhỏ nhất đó

INPUT: SECURITY.INP

 Dòng 1 chứa số nguyên dương N (1 ≤ N ≤ 105)

 Dòng 2 chứa N số nguyên, trong đó số nguyên thứ i là chi phí để xây dựng đồn cảnh sát tại địa điểm i (chi phí  ≤ 109)

 Dòng 3 chứa số nguyên M (0 ≤ M ≤ 3*105)

 M dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u và v (1 ≤ u, v ≤ n; u ≠ v) biểu diễn một con đường một chiều nối từ địa điểm u tới v Không có nhiều hơn 1 con đường nối giữa 2 địa điểm

OUTPUT: SECURITY.OUT

 Một dòng duy nhất chứa hai số, số thứ nhất là chi phí nhỏ nhất để xây dựng các đồn cảnh sát, số thứ hai là số phương án xây dựng (mod (109+7))

Ví dụ:

* Hướng dẫn thuật toán:

- Sử dụng thuật toán Tajan để tìm các thành phần liên thông mạnh, tại mỗi thành phần liên thông mạnh sẽ xây dựng một đồn cảnh sát có chi phí xây dựng là nhỏ nhất, và đếm

1: begin

low[u]:=min(low[u],number[v]); end;

Bài 3 Tàu cao tốc

Có n điểm tập trung dân cư đông đúc Các điểm này được

đánh số từ 1 đến n (1 ≤ n ≤ 104) Mạng lưới giao thông công

cộng là m đường xe lửa cao tốc một ray, mỗi đường nối một

cặp điểm dân cư và chạy hai chiều (0 ≤ m ≤ 105), và mọi cặp

điểm đều có thể đi đến được với nhau Để tránh sự va chạm

giữa các con tàu cao tốc khi chúng có thể đi ngược chiều trên

cùng một đường, chính quyền thành phố quyết định sửa lại

các con đường đó thành một chiều Tuy nhiên, sau khi thay đổi thì lại có một vấn đề bất cập sảy ra, đó là: tồn tại các cặp điểm tập trung dân cư không thể đi đến được nhau Chính vì vậy, chính quyền lại thêm một quyết định nữa, đó là sẽ xây dựng thêm một số ít nhất các tuyến đường mới để đảm bảo từ một điểm bất kỳ có thể đi tới điểm bất kỳ khác bằng tàu cao tốc

Ví dụ, với n = 5 và hiện có 4 đường: 1  2, 2  3, 1  4 và 4  5 Để đảm bảo yêu cầu

đã nêu, người ta cần xây dựng ít nhất 2 đường mới, chẳng hạn 5  3 và 3  1

Yêu cầu: Cho n, m và các cặp (a, b) mô tả mạng giao thông sau khi đã sửa thành đường

1 chiều Mỗi cặp (a, b) xác định tồn tại đường tàu a  b Hãy xác định số lượng tối thiểu

các đường cần xây dựng thêm

Dữ liệu: Vào từ file văn bản MONORAIL.INP:

 Dòng đầu tiên chứa 2 số nguyên n và m,

 Mỗi dòng trong m dòng tiếp theo chứa 2 số nguyên a và b

Kết quả: Đưa ra file văn bản MONORAIL.OUT một số nguyên – số đường mới

* Hướng dẫn thuật toán:

- Sử dụng Tajan để tìm các thành phần liên thông mạnh

- Mỗi thành phần liên thông mạnh thuộc 1 trong 3 loại sau:

+ Loại 1: Thành phần liên thông chỉ có cung đi ra mà không có cung đi vào (ví dụ đỉnh 1 trong hình trên)

+ Loại 2: Thành phần liên thông có cả cung đi ra và cả cung đi vào (ví dụ đỉnh 2

Từ đó hình thành cách giải như sau:

- Đếm số thành phần liên thông loại 1 (gọi là d1) và loại 3 (gọi là d3)

- Kết quả của bài toán chính là max(d1,d3)

if cs[chot[u]] = 0 then cs[chot[u]] := 1

else if cs[chot[u]] = 3 then cs[chot[u]] := 2;

if cs[chot[v]] = 0 then cs[chot[v]] := 3

else if cs[chot[v]] = 1 then cs[chot[v]] := 2; end;

if cs[i] = 1 then inc(d1)

else if cs[i] = 3 then inc(d2);

Cho trước 2 đỉnh s và t, hãy cho biết số thứ tự của lệnh add đầu tiên mà sau thời điểm thực hiện lệnh add đó đỉnh s có thể đi tới được đỉnh t theo một số cung của đồ thị

Input

 Dòng đầu chứa 3 số nguyên m ≤ 105, s, t (s ≠ t)

 M dòng tiếp theo, mỗi dòng chứa 2 số nguyên u, v thế hiện lệnh add(u, v)

* Hướng dẫn thuật toán

- Đề bài cho tối đa 109 đỉnh nhưng số lượng cạnh chỉ tốt đa là 105, nên thực tế số đỉnh chỉ cần dùng đến 105 đỉnh mà thôi Từ đó trước hết ta sẽ rời rạc hóa các đỉnh <=109 về các đỉnh <= 105

- Tiếp theo, sử dụng thuật toán tìm kiếm nhị phân kết hợp DFS để giải quyết bài toán Mỗi lần chặt nhị phân số cung để tìm số lần thêm cung tối thiểu, ta sử dụng thuật toán DFS để tìm đường đi từ s đến t

const int nmax = 1e5+5;

vector <int> adj[nmax];

map <int,int> M;

int dd[nmax];

Bài 5 Liên thông – đề thi thử QG 2012 – Hà Nam

Cho một đồ thị vô hướng gồm 𝑛 đỉnh đánh số từ 1 tới 𝑛 và 𝑚 cạnh đánh số từ 1 tới 𝑚 Cạnh thứ 𝑖 nối giữa hai đỉnh 𝑢𝑖, 𝑣𝑖 Nếu ta xoá đi một đỉnh nào đó của đồ thị, số thành phần liên thông của đồ thị có thể tăng lên Nhiệm vụ của bạn là với mỗi đỉnh, hãy tính xem nếu ta xoá đỉnh đó đi thì đồ thị mới nhận được có bao nhiêu thành phần liên thông

Dữ liệu: Vào từ file văn bản GRAPH_.INP

 Dòng đầu chứa hai số nguyên dương 𝑛, 𝑚 (𝑛 ≤ 20000; 𝑚 ≤ 50000)

 𝑚 dòng sau, dòng thứ 𝑖 chứa hai số nguyên dương 𝑢𝑖, 𝑣𝑖

Kết quả: Ghi ra file văn bản GRAPH_.OUT

 𝑛 dòng, dòng thứ 𝑗 cho biết số thành phần liên thông của đồ thị nếu ta xóa đi đỉnh

* Hướng dẫn thuật toán

- Đây là bài toán điển hình về tìm khớp trên đồ thị Nếu đỉnh u không phải là khớp thì số lượng thành phần liên thông không thay đổi, nếu đỉnh u là khớp thì số lượng thành phần liên thông sẽ được tăng lên

- Vấn đề ở đây là làm thế nào đếm được số lượng thành phần liên thông sau khi đã loại

bỏ một khớp u ra khỏi đồ thị Có thể giải quyết vấn đề này như sau: trong quá trình DFS

sử dụng thêm một mảng để lưu số lượng đỉnh con của đỉnh u là slcon[u] Khi đó nếu số lượng thành phần liên thông ban đầu của đồ thì là k thì tiếp theo sẽ có hai khả năng như sau:

+ Khả năng 1: u là khớp nhưng không phải đỉnh gốc của DFS thì số lượng thành phần liên thông sau khi xóa đỉnh khớp u là: k + slcon[u]

+ Khả năng 2: u là khớp nhưng lại là đỉnh gốc của DFS thì số lượng thành phần liên thông sau khi xóa đỉnh khớp u là: k + slcon[u] – 1

{

int j = ke[i][k];

if(fa[j] == -1) {

low[i] = min(low[i], num[j]);

Bài 6 Cảnh sát (spoj)

Để giúp nắm bắt bọn tội phạm trên chạy, cảnh sát được giới thiệu một hệ thống máy vi tính Khu vực được quản lý bởi cảnh sát thành phố có chứa N thành phố liên thông bằng

E tuyến đường hai chiều kết nối chúng Các thành phố được dán nhãn từ 1 đến N

Để xử lý trong trường hợp khản cấp, cảnh sát nhờ bạn xây dựng một chương trình phần mềm trả lời hai câu hỏi sau truy vấn:

1 Xem xét việc hai thành phố A và B, và một đường kết nối giữa thành phố G1 và G2 Bọn tội phạm có thể đi từ thành phố A đến thành phố B, nếu con đường đó bị chặn và bọn tội phạm không thể sử dụng nó?

2 Xem xét ba thành phố A, B và C bọn tội phạm có thể đi được từ thành phố A đến thành phố B nếu toàn bộ thành phố C là được phong tỏa và bọn tội phạm có thể không được nhập vào thành phố này?

Viết một chương trình để thực hiện các mô tả hệ thống

Dữ liệu vào từ tệp: POLICIJA.INP

 Dòng đầu tiên chứa hai số nguyên N và E (2N100 000 1,  E 500 000), là số lượng các thành phố và tuyến đường

 E dòng tiếp theo mỗi dòng ghi hai số thể hiện một tuyến đường

 Dòng tiếp theo ghi số K là số câu hỏi cần truy vấn

 K dòng tiếp theo mỗi dòng ghi một lại câu hỏi:

 1 A B G1 G2: cho loại câu hỏi thứ nhất (1 A, B, G , G1 2N ), A,B, G1,G2 khác nhau

 2 A B C: cho loại câu hỏi thứ hai (1A, B, CN), A,B,C khác nhau

Dữ liệu ra vào tệp: POLICIJA.OUT

 Tương ứng với mỗi câu truy vấn có một câu trả lời ghi trên một dòng của tệp kết quả Câu trả lời cho một truy vấn có thể là "no" hay "yes"

Ví dụ

POLICIJA.INP POLICIJA.OUT

no yes

* Hướng dẫn thuật toán:

Cách 1:O(N * Q):

Với mỗi truy vấn:

 A B G1 G2: bỏ cạnh (G1, G2) rồi DFS lại xem A có đến được B hay không

 A B C : bỏ đỉnh C rồi DFS lại xem A có đến được B hay không

Cách 2: O(Q log N):

Ta dựng mảng p[i, j] = tổ tiên bậc 2j của i Công thức : p[i, j] = p[p[i, j – 1], j – 1]

 mảng num[i] = thời gian đỉnh i được thăm trong thủ tục DFS

 mảng fin[i] = thời gian đỉnh i thoát ra khỏi thủ tục DFS

 u thuộc nhánh DFS gốc v (num[u] >= num[v]) and (fin[u] <= fin[v]) (hàm Kt(u, v))

Với truy vấn (A, B, G1, G2), giả sử G2 thuộc nhánh DFS gốc G1:

 Nếu G1 không là cha trực tiếp của G2 => in ‘yes’

 Nếu (G1, G2) không là câu => in ‘yes’

 Nếu (G1, G2) là câu:

o Nếu Kt(u, G2) = Kt(v, G2) => in ‘yes’

o Nếu không in ‘no’

Với truy vấn (A, B, C)

 Nếu A, B cùng không thuộc nhánh DFS gốc C  not Kt(A, C) and not Kt(B, C)

o Nếu không in ‘no’

 Nếu C, B thuộc nhánh DFS gốc A: Gọi x là tổ tiên xa nhất nhưng vẫn là thuộc nhánh DFS gốc C của B

o Nếu x có thể lên được tổ tiên của C  low[x] < num[C] thì in ‘yes’

o Nếu không in ‘no’

void init() {

V.resize(n+1);

sort( E.begin(), E.end() );

V[0] = E.begin();

for( int i = 1; i <= n; ++i )

for( V[i] = V[i-1]; V[i] != E.end() && V[i]->u < i; ++V[i] );

}

inline vector<edge>::iterator begin( int u ) { return V[u]; }

inline vector<edge>::iterator end( int u ) { return V[u+1]; }

} graph;

vector<int> discover, finish, lowlink, depth;

int Time = 0;

vector< vector<int> > children;

void dfs( int u, int dad, int d ) {

discover[u] = lowlink[u] = Time++;

int is_descendant( int a, int b ) {

return discover[b] <= discover[a] && finish[a] <= finish[b];

}

int find_related_child( int me, int descendant ) {

int lo = 0, hi = children[me].size() - 1;

while( lo != hi ) {

int mid = (lo+hi) / 2;

if( discover[descendant] > finish[ children[me][mid] ] ) lo = mid+1; else if( finish[descendant] < discover[ children[me][mid] ] ) hi = mid-1;

else lo = hi = mid;

}

return children[me][lo];

}

int main( void ) {

scanf( "%d%d", &n, &m );

for( int i = 0; i < m; ++i ) {

if( is_descendant( c, d ) ) swap( c, d );

if( depth[d] != depth[c]+1 ) printf( "yes\n" );

else if( lowlink[d] < discover[d] ) printf( "yes\n" );

else if( is_descendant( a, d ) == is_descendant( b, d ) ) printf(

if( e == f ) printf( "yes\n" );

else if( lowlink[e] < discover[c] && lowlink[f] < discover[c] ) printf( "yes\n" );

else printf( "no\n" );

} else {

if( is_descendant( a, c ) ) swap( a, b );

int e = find_related_child( c, b );

if( lowlink[e] < discover[c] ) printf( "yes\n" );

else printf( "no\n" );

Bài 7 Đường đua dài nhất

Mạng giao thông của thành phố ByteLand có N nút giao thông Giữa hai nút giao thông

có tối đa một đường phố hai chiều nối trực tiếp giữa chúng Nhân dịp chào mừng kỷ niệm

100 năm ngày thành lập, Lãnh đạo thành phố quyết định tổ chức một cuộc đua xe đạp Đường đua xe đạp sẽ xuất phát từ một nút bất kỳ, qua một số nút khác và trở lại nút ban đầu sao cho không có nút nào (trừ nút xuất phát) đường đua qua đó hai lần Thật ngạc nhiên, mạng lưới giao thông của thành phố cho phép lập nhiều đường đua xe đạp như vậy

tuy nhiên: mỗi một đường phố sẽ thuộc không quá một đường đua thỏa mãn điều kiện

* Hướng dẫn thuật toán

- Đây là một bài toán tìm thành phần song liên thông với số lượng đỉnh lớn nhất và >=3

* Chương trình mẫu

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair

#define pii pair<int,int>

const int nmax = 5000;

int n,m,dd[nmax],num[nmax],low[nmax],id = 0,maxx = 0,cha[nmax],dem = 0; vector <int> adj[nmax],adj1[nmax];

set <pii> se;

Bài 8 Đường đi dài nhất

Cho đồ thị có hướng không có chu trình (DAG) Mỗi cạnh của đồ thị được gán trọng số

là một số nguyên

Giải các bài toán sau:

a) Tìm đường đi dài nhất từ đỉnh s đến đỉnh t

b) Đếm số lượng đường đi từ s đến đỉnh t

Input: DAG.INP

 Dòng đầu tiên ghi hai số nguyên dương n, m ( 5 5

1 n 3.10 ,1 m 5.10 ) lần lượt là

số đỉnh và số cạnh của đồ thị Các đỉnh đánh số từ 1 đến n

 Dòng thứ hai ghi hai số nguyên dương s, t (1≤s,t≤n, s≠t)

 m dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương a, b, c (1≤a, b≤n, a ≠b, |c| ≤103)

thể hiện có một cung một chiều nối từ đỉnh a đến đỉnh b có trọng số là c

 Dữ liệu đảm bảo rằng đồ thị không có chu trình

Output: DAG.OUT

 Dòng thứ nhất ghi độ dài của đường đi dài nhất từ s đến t Nếu không tồn tại đường

đi như vậy thì ghi "NO PATH" (không có dấu nháy kép)

 Dòng thứ hai ghi số lượng đường đi khác nhau có thể có từ s đến t Vì con số này

có thể rất lớn nên chỉ cần lấy phần dư của chúng khi chia cho 109+7

* Hướng dẫn thuật toán

- Gọi F[u], C[u] là đường đi dài nhất vầ số lượng đường đi từ đỉnh s đến đỉnh u, và khi đó F[t] và C[t] là hai kết quả của bài toán

- Xét cung (u,v): Dễ dàng suy ra công thức:

F[v] = max(F[u]) + w(u,v) (1) C[v] = C[v] + C[u] (2)

- Tuy nhiên quá trình duyệt DFS nếu không cẩn thận thì một đỉnh sẽ được duyệt nhiều lần và như vậy sẽ không đáp ứng được yêu cầu của bài toán về mặt thời gian

- Có thể giải quyết vấn đề trên như sau:

- Sử dụng DFS để đánh lại chỉ số thứ tự các đỉnh của đồ thị gọi là sắp xếp topo

- Từ sắp xếp topo khi đó sử dụng công thứ (1) và (2) ở trên

int x[maxn], slx, cl[maxn];

int kc[maxn], f[maxn];