Hai đồ thị vô hướng \(G\) và \(H\) được gọi là đẳng cấu nếu chúng có cùng số đỉnh và tồn tại một tương ứng một-một giữa các đỉnh của chúng sao cho: với hai đỉnh phân biệt bất kỳ của \(G\), có một cạnh nối chúng khi và chỉ khi có một cạnh nối hai đỉnh tương ứng trong \(H\).

Chẳng hạn, hai đồ thị dưới đây đẳng cấu, mặc dù hình vẽ của chúng trông khác nhau:

Một tương ứng một-một chứng minh hai đồ thị này đẳng cấu là \(a \leftrightarrow 1\), \(b \leftrightarrow 6\), \(c \leftrightarrow 8\), \(d \leftrightarrow 3\), \(g \leftrightarrow 5\), \(h \leftrightarrow 2\), \(i \leftrightarrow 4\), \(j \leftrightarrow 7\). Ngoài ra còn có những tương ứng khác.

Một đồ thị con của đồ thị \(G\) là một đồ thị có tập đỉnh và tập cạnh lần lượt là các tập con của tập đỉnh và tập cạnh của \(G\). Lưu ý rằng \(G\) cũng là một đồ thị con của chính nó. Hình dưới đây minh họa một đồ thị và một trong các đồ thị con của nó:

Ta nói đồ thị \(G\) chứa đồ thị \(H\) nếu có ít nhất một đồ thị con \(H'\) của \(G\) đẳng cấu với \(H\). Hình sau minh họa một đồ thị \(G\) chứa đồ thị \(H\):

Cho hai đồ thị vô hướng \(G\) và \(H\), hãy tạo một đồ thị con \(G'\) của \(G\) sao cho \(G'\) có cùng số đỉnh với \(G\) và không chứa \(H\). Có thể có nhiều đồ thị con thỏa mãn các điều kiện trên; hãy đưa ra một đồ thị như vậy có càng nhiều cạnh càng tốt.

Thuật toán cơ sở

Có lẽ chiến lược đơn giản nhất là xét các cạnh của \(G\) theo thứ tự chúng được biểu diễn trong tệp dữ liệu vào, rồi lần lượt thử thêm từng cạnh vào \(G'\), kiểm tra ở mỗi bước xem \(G'\) có chứa \(H\) hay không. Chỉ giữ lại cạnh nếu sau khi thêm cạnh đó, \(G'\) vẫn không chứa \(H\). Một cài đặt đúng của thuật toán tham lam này sẽ nhận được một phần điểm, nhưng còn có những chiến lược tốt hơn nhiều.

Dữ liệu vào

Đây là bài chỉ nộp kết quả. Bạn được cung cấp \(10\) tệp forbidden1.in đến forbidden10.in. Mỗi tệp forbiddenK.in có cấu trúc như sau:

• Dòng đầu chứa hai số nguyên cách nhau bởi một dấu cách, lần lượt là \(m\) và \(n\).
• \(m\) dòng tiếp theo biểu diễn ma trận kề của \(H\). Mỗi dòng chứa \(m\) số nguyên cách nhau bởi dấu cách và tương ứng với một đỉnh của \(H\), theo thứ tự \(1,\ldots,m\). Phần tử thứ \(i\) trên dòng thứ \(j\) của phần này bằng \(1\) nếu có cạnh nối hai đỉnh \(i\) và \(j\) trong \(H\), và bằng \(0\) nếu không có.
• \(n\) dòng tiếp theo biểu diễn ma trận kề của \(G\). Mỗi dòng chứa \(n\) số nguyên cách nhau bởi dấu cách và tương ứng với một đỉnh của \(G\), theo thứ tự \(1,\ldots,n\). Phần tử thứ \(i\) trên dòng thứ \(j\) của phần này bằng \(1\) nếu có cạnh nối hai đỉnh \(i\) và \(j\) trong \(G\), và bằng \(0\) nếu không có.

Như vậy, ngoại trừ dòng đầu tiên, dữ liệu vào chính là hai ma trận kề của \(H\) và \(G\), theo thứ tự này.

Dữ liệu ra

Bạn phải nộp \(10\) tệp kết quả, mỗi tệp ứng với một tệp dữ liệu vào. Tệp forbiddenK.out phải có cấu trúc sau:

• Dòng đầu là dòng tiêu đề, có dạng chính xác #FILE forbidden K, trong đó \(K\) là số từ \(1\) đến \(10\) ứng với tệp dữ liệu vào đang được giải.
• Dòng thứ hai chứa một số nguyên \(n\).
• \(n\) dòng tiếp theo biểu diễn ma trận kề của \(G'\). Mỗi dòng chứa \(n\) số nguyên cách nhau bởi dấu cách và tương ứng với một đỉnh của \(G'\), theo thứ tự \(1,\ldots,n\). Phần tử thứ \(i\) trên dòng thứ \(j\) của phần này bằng \(1\) nếu có cạnh nối hai đỉnh \(i\) và \(j\) trong \(G'\), và bằng \(0\) nếu không có.

Như vậy, ngoại trừ hai dòng đầu, dữ liệu ra chính là ma trận kề của \(G'\).

Ràng buộc

• \(3 \le m \le 4\), trong đó \(m\) là số đỉnh của \(H\).
• \(3 \le n \le 1\,000\), trong đó \(n\) là số đỉnh của \(G\).

Chấm điểm

Phiên bản này sử dụng quy tắc chấm điểm cố định của LQDOJ, phỏng theo cách chuẩn hóa của bản chuyển thể trên Codeforces. Điểm không phụ thuộc vào bài nộp của người chơi khác và không tái hiện điểm lịch sử IOI 2006.

Mỗi tệp chiếm \(10\) điểm trong tổng số \(100\) điểm. Kết quả sai định dạng, thêm cạnh không có trong \(G\), thay đổi số đỉnh hoặc chứa \(H\) nhận \(0\) điểm cho tệp đó. Ma trận phải đối xứng, chỉ chứa \(0,1\) và có đường chéo bằng \(0\). Việc chứa \(H\) xét theo đồ thị con thông thường, không yêu cầu đồ thị con cảm sinh.

Với kết quả hợp lệ, gọi \(E_y\) là số cạnh giữ lại, \(E_b\) là mốc cơ sở và \(T\) là mốc đạt đủ điểm trong bảng sau. Phần trăm điểm của tệp là:

Các mốc \(T\) được chọn từ số cạnh của các cách xây dựng trong lời giải chính thức; riêng tệp \(7\) dùng mốc \(197\) được chứng minh từ dữ liệu công khai. Đây là các mốc của phiên bản này, không phải khẳng định mọi mốc đều tối ưu. Kết quả hợp lệ vượt \(T\) vẫn nhận đủ điểm và không làm thay đổi mốc chấm.

Trong kỳ thi này, điểm từng tệp là điểm cao nhất của tệp đó trên tất cả các lần nộp của bạn, rồi cộng các điểm này để tính tổng. Đây là quy tắc tổng hợp điểm của phiên bản chuyển thể, không phải quy tắc lịch sử IOI 2006.

Tổng điểm là tổng của \(10p/100\) trên cả \(10\) tệp. Không làm tròn điểm từng tệp về số nguyên. Đồ thị không có cạnh nhận \(0\) điểm. Nộp một tệp ZIP chứa trực tiếp forbidden1.out đến forbidden10.out, không đặt trong thư mục con. Tệp thiếu nhận \(0\) điểm; các tệp còn lại được chấm độc lập. ZIP tối đa \(10\) MiB; mỗi tệp kết quả phải nhỏ hơn \(8\) MiB, mỗi dòng ma trận tối đa \(8192\) ký tự.

Ví dụ

3 5
0 1 0
1 0 1
0 1 0
0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
0 0 0 1 0

#FILE forbidden K
5
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Nguồn

IOI 2006, ngày thi thứ nhất: Forbidden Subgraph, bản tiếng Anh 1.2. Tác giả đề bài: Francisco Zaragoza (Mexico).

10 tệp dữ liệu vào.