Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị



tải về 418.79 Kb.
trang2/8
Chuyển đổi dữ liệu21.08.2016
Kích418.79 Kb.
#25787
1   2   3   4   5   6   7   8

Chuyên đề DFS

  1. Quảng cáo

Mã bài: ADS


Nhân dịp Tết sắp đến công ty Jelly-for-Kids quyết định tăng cường việc quảng bá sản phẩm đến người tiêu dùng. Vì thế giám đốc marketing, ông Fruit-Jelly muốn gửi đi số lượng nhân viên tối đa có thể, làm nhiệm vụ tiếp thị tại đại lý trong thành phố

Trong thành phố có m con đường, n đại lý bán kẹo (đánh số từ 1 đến n). Mỗi con đường chỉ nối trực tiếp giữa 2 đại lý, và được ký hiệu bằng chỉ số của 2 đại lý mà nó nối. Đồng thời, giữa 2 đại lý bất kỳ có không quá 1 con đường nối chúng

Ông Fruit-Jelly nghĩ rằng, ông ta sẽ quản lý nhân viên dễ hơn nếu xếp mỗi người tiếp thị trên những hành trình có tính chất thứ tự. Tức là những đại lý bán kẹo trên hành trình đó thỏa các điều kiện sau

Có đường nối trực tiếp giữa 2 đại lý liên tiếp nhau trên hành trình

Từ một đại lý bất kỳ trong hành trình có thể đi qua tất cả các đoạn đường trong hành trình đó rồi trở về nơi xuất phát mà không đi qua đoạn đường nào quá một lần

Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị.

Mỗi nhân viên chỉ di chuyển trên hành trình mà anh ta được phân công. Hãy tính số lượng nhân viên tối đa mà ông Fruit-Jelly có thể xếp việc, và hành trình cụ thể mà mỗi người được xếp.

Input


Dòng đầu là 2 số tự nhiên N và M (N<=2000) (M<=5000)

Trong M dòng tiếp theo, mỗi dòng ghi 2 số nguyên mô tả một đoạn đường, mỗi đoạn đường được mô tả bởi chỉ số của 2 đại lý mà nó nối.


Output


Dòng đầu tiên ghi Q là số lượng nhân viên tối đa tìm được

Example

ADS.INP

ADS.OUT

5 6

1 2


2 4

4 5


3 5

1 3

2 3


2

  1. Truyền tin

Mã bài: MESSAGE


Một lớp gồm N học sinh, mỗi học sinh cho biết những bạn mà học sinh đó có thể liên lạc được (chú ý liên lạc này là liên lạc một chiều : u có thể gửi tin tới v nhưng v thì chưa chắc đã có thể gửi tin tới u).

Thầy chủ nhiệm đang có một thông tin rất quan trọng cần thông báo tới tất cả các học sinh. Để tiết kiệm thời gian, thầy chỉ nhắn tin tới 1 số học sinh rồi sau đó nhờ các học sinh này nhắn lại cho tất cả các bạn mà các học sinh đó có thể liên lạc được, và cứ lần lượt như thế làm sao cho tất cả các học sinh trong lớp đều nhận được tin .

Hãy tìm một số ít nhất các học sinh mà thầy chủ nhiệm cần nhắn.

Input


- Dòng đầu là N, M (N <= 800, M là số lượng liên lạc 1 chiều)

- Một số dòng tiếp theo mỗi dòng gồm 2 số u , v cho biết học sinh u có thể gửi tin tới học sinh v


Output


- Gồm 1 dòng ghi số học sinh cần thầy nhắn tin.

Example

MESSAGE.INP

MESSAGE.OUT

12 15

1 3


3 6

6 1


6 8

8 12


12 9

9 6


2 4

4 5


5 2

4 6


7 10

10 11


11 7

10 9


2

  1. Bộ ba cao thủ

Mã bài: NKTRIO


Ở thời loạn, giang hồ có rất nhiều cao thủ võ lâm, mỗi người trong số họ lại có những tuyệt chiêu. Nếu 2 cao thủ giang hồ so tài với nhau thì từ những sở trường và sở đoản của họ, ta có thể biết trước được cao thủ nào sẽ thắng. Những cao thủ đang có ở VNOI như conankudo, gothdn, kaiel, nahnhnahk, pirate... đang muốn thi tài để xem ai được chọn làm bộ ba cao thủ.

Để mưu nghiệp lớn, minh chủ võ lâm Nuga cần tìm ra một bộ ba trong số các cao thủ giang hồ hiện tại. Để các cao thủ này quy phục dưới trướng của mình và không làm phản, Nuga muốn bộ ba cao thủ này có thể khắc chế được nhau; điều này có nghĩa là nếu 3 cao thủ được chọn là A, B và C thì A phải thắng được B, B phải thắng được C và C phải thắng được A.

Bạn hãy giúp Nuga chọn ra một bộ ba cao thủ thoả mãn yêu cầu của ông.

Dữ liệu:


Dòng đầu tiên ghi n là số cao thủ trên giang hồ (3 ≤ n ≤ 1000)

Tiếp theo là n dòng, mỗi dòng có n số. A[i,j] = 1 là người i thắng j. Dữ liệu luôn đảm bảo A[i,j] + A[j,i] = 1. A[i,i] = 0 với mọi i.


Kết quả:


Ghi ra ba số nguyên A, B và C là thứ tự của ba cao thủ thoả mãn A thắng B, B thắng C và C thắng A. Trong trường hợp có nhiều cách lựa chọn, bạn chỉ cần chỉ ra một cách; trong trường hợp không có cách lựa chọn thoả mãn yêu cầu, ghi ra ba số -1.

Ví dụ:

NKTRIO.INP

NKTRIO.OUT

5

0 1 1 1 0

0 0 1 1 0

0 0 0 0 1

0 0 1 0 0

1 1 0 1 0
2 3 5

3

0 1 1


0 0 1

0 0 0


-1 -1 -1

  1. Mạng máy tính an toàn

Mã bài: SAFENET2


Có n máy tính đánh số từ 1 đến n và m dây cáp mạng,giữa 2 máy tính có thể có một hoặc nhiều đường dây cáp mạng nối chúng,không có cáp mạng nối một máy với chính nó.Hai máy tính có thể truyền dữ liệu cho nhau nếu có đường cáp nối trực tiếp giữa chúng hoặc truyền qua một số máy trung gian.

Một tập S các máy tính được gọi là hệ thống an toàn nếu dù một máy tính bất kỳ bị tấn công (do sự tò mò của người dân :-(,cứ thích truy cập và hack những trang cấm :-( ) thì trong số những máy tính còn lại,những máy tính thuộc tập S vẫn có thể truyền được dữ liệu cho nhau. Xác định số lượng lớn nhất có thể các máy tính của tập S


Input


-Dòng 1 chứa 2 số nguyên n,m(1<=n<=30.000,0<=m<=100.000)

-m dòng tiếp theo ghi thông tin về các dây cáp mạng,gồm 2 chỉ số của 2 máy được dây đó nối trực tiếp


Output


Ghi một số nguyên duy nhất là số lượng máy tính lớn nhất tìm đc

Example


SAFENET2.INP

SAFENET2.OUT

8 10
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 8
8 1

4

  1. Vòng đua xe đạp

Mã bài: BIC


Một vòng đua xe đạp được tổ chức trên N thành phố, đánh số từ 1 đến N. Có M đường nối (một chiều) giữa các thành phố. Vòng đua bắt đầu từ thành phố 1 và kết thúc tại thành phố 2.

Yêu cầu


Hỏi có bao nhiêu cách tổ chức các vòng đua? (Biết hai vòng đua là khác nhau nếu chúng không sử dụng các tuyến đường như nhau)

Dữ liệu


Dòng 1: N, M

M dòng tiếp theo: mỗi dòng chứa hai số nguyên A, B, cho biết có một đường nối giữa thành phố A và thành phố B

Các thành phố có thể nối với nhau bởi nhiều hơn một con đường

Kết qủa


Gồm 1 dòng duy nhất: số cách tổ chức các vòng đua. Nếu kết qủa có nhiều hơn 9 chữ số, chỉ cần in ra 9 chữ số cuối cùng. Nếu có vô số cách tổ chức các đường đua, in ra “inf”.

Giới hạn


  • 1 ≤ N ≤ 104

  • 1 ≤ M ≤ 105

Ví dụ


BIC.INP

BIC.OUT

8 14

6 7


6 8

7 5


5 2

5 3


4 8

1 6


5 2

7 5


6 4

1 4


5 2

7 4


8 3

6

2 2

1 2


2 1

inf

  1. Xây cầu

Mã bài: BRIDGES


Đất nước Delta là quốc đảo lớn trên thế giới. Đất nước gồm N đảo nhỏ được đánh số từ 1 đến N. Việc đi lại giữa các đảo là rất khó khăn. Vì kinh tế còn rất kém phát triển, nhà nước phải khó khăn lắm mới mở được N – 1 tuyến phà biển để người dân người dân có thể đi lại được giữa hai đảo bất kì. Cách đây không lâu, đất nước mới nhận được sự đầu tư lớn của các nước tư bản. Nhà vua quyết định xây mới K cây cầu để thay cho K tuyến phà. Các cây cầu mới được xây dựng sẽ nối liền hai đảo mà trước đây có tuyến phà nối trực tiếp. Nhà vua muốn tính toán để chọn K tuyến phà nào để xây thành cầu sau cho tổng thời gian để đi lại giữa mọi cặp đỉnh là nhỏ nhất. Tức là: đạt giá trị nhỏ nhất. Trong đo TA B là thời gian đi từ đảo A đến đảo B. Bạn hãy giúp nhà Vua tính toán chọn ra K trong số N - 1 tuyến phà để thay thế bằng cầu.

Input


  • Dòng thứ nhất ghi 4 số nguyên N, K, VP, VC trong đó VP là vận tốc nếu đi bằng phà và VC là vận tốc nếu đi bằng cầu. VP và VC có đơn vị là m/s

  • N – 1 dòng tiếp theo, mỗi dòng ghi 3 số U V L thể hiện giữa đảo U và đảo V đã có một tuyến phà, và khoảng cách giữa U và V là L mét.

Output


In ra K số là số hiệu của tuyến phà cần được thay thế bằng cầu.

Giới hạn


  • 1 ≤ K < N ≤ 10 000

  • 1 ≤ VP, VC ≤ 100 000

  • 1 ≤ LU V ≤ 106

  • Thời gian: 1s/test

Example

BRIDGES.INP

BRIDGES.OUT

6 2 1 2

1 2 5


3 2 6

1 4 4


4 6 4

4 5 5

1 3





tải về 418.79 Kb.

Chia sẻ với bạn bè của bạn:
1   2   3   4   5   6   7   8



Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý
    Quê hương
BÁO CÁO
Tài liệu