g773: 實境節目選角 (Casting)
Tags :
Accepted rate : 24人/35人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-12-02 12:49

Content

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

Input

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

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

Output

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

Sample Input #1
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
Sample Output #1
2
Sample Input #2
3
0 0 0
0 0 0
0 0 0
Sample Output #2
3
Sample Input #3
3
0 1 0
1 0 0
0 0 0
Sample Output #3
2
測資資訊:
記憶體限制: 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
Hint :

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

Tags:
出處:
TOI練習賽202111潛力組 [管理者:
fire5386 (Penguin07)
]


ID User Problem Subject Hit Post Date
28364
r1cky (木叢欉木叢)
g773
Java 解題心得
285 2021-12-05 12:33