Các lượt nộp

Danh sách bài

Báo lỗi

solution

Đề bài: [Toán rời rạc] Bao đóng bắc cầu (Warshall)

Bao đóng bắc cầu của quan hệ $R$ là quan hệ bắc cầu nhỏ nhất chứa $R$ : có $i \to j$ nếu tồn tại một dãy $i \to \cdots \to j$ theo $R$ .

Thuật toán Warshall: với mỗi đỉnh trung gian $k$ , nếu $M_{ik}=1$ và $M_{kj}=1$ thì đặt $M_{ij}=1$ .

Cho ma trận quan hệ $n\times n$ , hãy in ma trận bao đóng bắc cầu.

Ví dụ: với $1\to2$ và $2\to3$ , bao đóng bổ sung $1\to3$ .

Định dạng đầu vào:
Dòng 1: $n$ . $n$ dòng tiếp theo: ma trận quan hệ ( $0/1$ ).
Ràng buộc đầu vào:
$1 \le n \le 300$ .
Định dạng đầu ra:
$n$ dòng: ma trận bao đóng bắc cầu, mỗi hàng $n$ số cách nhau bởi dấu cách.

Ví dụ:

Đầu vào:

Đầu ra:

0 1 1
0 0 1
0 0 0

Giải thích:

Từ $1\to2\to3$ bao đóng thêm $1\to3$, cho hàng 1 là "0 1 1".

Đang tải editor...