//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Mạch in

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 14


Đề bài


Mạch in là một bảng gồm các nút nằm trên các nút của một lưới hình chữ nhật và các đoạn dây dẫn noói các nút kề nhau (theo chiều đứng hoặc ngang). Mạch được gọi là liên thông nêu hai nút bất kỳ được nối với nhau bởi dãy các đoạn dây dẫn. Cho một mạch in trong đó đã có một số đoạn dây dẫn nối một loạt các cặp nút kề nhau. Cần tìm cách bổ sung các đoạn dây đẫn để đảm bảo mạch in thu được là liên thông và với chi phí nhỏ nhất. Biết rằng: chi phí của đoạn dây nối theo chiều đứng là 1, còn theo chiều ngang là 2.

dt14

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

  • Dòng đầu tiên chứa hai số nguyên N và M. N (1£N£100 là số dòng và M (1 <= M <= 100) là số cột của lưới. Mỗi nút trên của lưới được xác định bởi hai toạ độ: Nút ở góc trái trên có toạ độ (1,1), nút ở góc phải dưới có toạ độ (N,M)
  • Mỗi một trong số N dòng tiếp theo chứa M sốnguyên. Số nguyên ở tên dòng i và cột j của dòng này mô tả đoạn dây nối giữa cặp nối (i,j) và (i+1,j) cũng như giữa cặp nút (i,j) và (i,j+1) theo qui tắc sau:
  • 0 có nghĩa là không có đoạn dây nối giữa (i,j) và (i+1,j) cũng như giữa cặp nút (i,j) và (i,j+1)
  • 1 có nghĩa là có đoạn dây nối giữa cặp nút (i,j) và (i+1,j);
  • 2 có nghĩa là có đoạn dây nối giữa cặp nút (i,j) và (i,j+1);
  • 3 có nghĩa là cả cặp nút (i,j) và (i+1,j) và (i,j) và (i,j+1) đều được nối với nhau

Kết quả: ghi ra file văn bản CIRCUIT.OUT:

  • Dòng đầu tiên chứa hai số nguyên K và V, trong đó K là số đoạn nối cần bổ sung trong cách bổ sung với chi phí nhỏ nhất tìm được còn V là chi phí tương ứng.
  • Mỗi một trong số K dòng tiếp theo chứa ba số nguyên i,j và d, trong đó (i,j) là toạ độ của nút còn d chỉ nhận một trong hai giá trị 1 và 2. d=1 cho biết phải nối nút (i,j) với (i+1,j) và d=2 cho biết phải nối nút (i,j) với (i,j+1)

Ví dụ: Xem minh hoạ trong hình 1 và 2

CIRCUIT.INP CIRCUIT.OUT
4 5

2 1 1 2 1

0 3 0 1 0

3 0 0 3 1

0 2 0 2 0

5 6

1 1 1

3 2 1

3 3 1

3 3 2

2 5 1


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 210,510 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: