g773. 實境節目選角 (Casting) - 高中生程式解題系統

內容

電視台想要錄製實境節目內容大致為挑戰者們經過彼此不斷競爭與淘汰最後一位沒被淘汰的挑戰者即為贏家。假設有 $N$ 位報名者，編號從 $1 N$ ；為了避免玩家彼此相互串通的情形發生，主辦方會從 $N$ 位報名者中選出 $K$ 位挑戰者，這 $K$ 位彼此不能是朋友。給定主辦方所調查報名者的交友關係，請找出 $K$ 最大可以是多少。
舉例而言：
一開始有 $N = 4$ 位報名者，調查得知1和2是朋友、2和3是朋友、3和4是朋友以及4和1是朋友，則最多可以同時有 $K = 2$ 位挑戰者參加節目（1、3或2、4）。

輸入說明

第一行有 1 個正整數 $N$ $(1 \leq N \leq 17)$ 分別表示有 $N$ 位報名者。

第 2 行到第 $N + 1$ 行中每行都有 $N$ 個非負整數，彼此間以一個空白隔開，其中第 $i + 1$ 行從左至右數來第 $j$ 個數字以 $A_{i j}$ 表示。如果 $A_{i j} = 1$ 表示 $i$ 和 $j$ 是朋友；如果 $A_{i j} = 0$ 表示他們不是朋友 $（ 0 \leq A_{i j} \leq 1 、 A_{i j} = A_{j i} 、 A_{i i} = 0 ）$ 。

輸出說明

請輸出一個正整數，表示最多可以有幾位挑戰者。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

範例輸入 #3

範例輸出 #3

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1K
不公開測資點#5 (5%): 1.0s , <1K
不公開測資點#6 (5%): 1.0s , <1K
不公開測資點#7 (5%): 1.0s , <1K
不公開測資點#8 (5%): 1.0s , <1K
不公開測資點#9 (5%): 1.0s , <1K
不公開測資點#10 (5%): 1.0s , <1K
不公開測資點#11 (5%): 1.0s , <1K
不公開測資點#12 (5%): 1.0s , <1K
不公開測資點#13 (5%): 1.0s , <1K
不公開測資點#14 (5%): 1.0s , <1K
不公開測資點#15 (5%): 1.0s , <1K
不公開測資點#16 (5%): 1.0s , <1K
不公開測資點#17 (5%): 1.0s , <1K
不公開測資點#18 (5%): 1.0s , <1K
不公開測資點#19 (5%): 1.0s , <1K

提示：

評分說明
此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (30分)： $N \leq 3$ 。
第二組 (70分)：沒有特別限制。

標籤:

出處:

TOI 練習賽 202111 潛力組 [管理者： fire5386 (becaidorz) ]

編號	身分	題目	主題	人氣	發表日期
28364	r1cky (hehe)	g773	Java 解題心得	759	2021-12-05 12:33