TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

28.0% (7/25)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲。而現在要講的,是殿壬在念「孔乙己」的故事。

你以為殿壬是真的在念「孔乙己」嘛?那就大錯特錯了,「孔乙己」已經是一篇對殿壬來講太過時的文章了,他讀的是「Tan乙己」,內容如下:

Tan乙己是站着喝酒而穿長衫的唯一的人。他對人說話,總是滿口費氏 $O(1)$ ,教人半懂不懂的。因爲他姓Tan,別人便從描紅紙上的「 $O(1)$ 大人Tan乙己」這半懂不懂的話裏,替他取下一個綽號,叫作Tan乙己。Tan乙己一到店,所有喝酒的人便都看着他笑,有的叫道,「Tan乙己,你臉上又添上新傷疤了!」他不回答,對櫃裏說,「溫兩碗酒,要import math。」便排出 $\pi + e$ 文大錢。他們又故意的高聲嚷道,「你一定又說了費氏數列的東西了!」Tan乙己睜大眼睛說,「你怎麼這樣憑空汚人清白……」「什麼清白?我前天親眼見你說了費氏是 $O(1)$ ,吊着罵。」Tan乙己便漲紅了臉,額上的青筋條條綻出,爭辯道,「費氏不能算 $O(logN)$ …… $O(1)$ !……月球人的事,能算 $O(logN)$ 麼?」接連便是難懂的話,什麼「月球電腦」,什麼「猴子」之類,引得衆人都鬨笑起來:店內外充滿了快活的空氣。

上述文章就是殿壬當時在讀的「Tan乙己」。因為殿壬實在是太殿了,所以他只想到:如果把圖論中,任意兩個點之間的邊用月球電腦來連接,這兩個點可能就有可能連通了!

於是,很殿的殿壬,就想到了一題很殿的題目,但是因為題目實在是太殿了,他不小心把自己給殿焦了,於是他想請你幫忙解決這個問題,題目如下:

給你一張 $N$ 點的圖,以及一個 $N \times N$ 的矩陣。點從 $1$ 到 $N$ 編號。對於所有的 $i$ 介於 $[1,N]$ ,$a_{ii} = 0$ 。如果編號為 $i$ 的點跟編號為 $j$ 的點之間有一條邊相鄰的話, $a_{ij} = a_{ji} = 1$ ,否則 $a_{ij} = a_{ji} = 0$ 。

另外,對於編號為 $i$ 的點,都有一個數值 $w_i$ ,代表這個點的權重!

現在,定義一個頂點的集合 $V$ 是獨立集是獨立集,若且唯若不存在兩個 相異 在 $V$ 的點 $x$ 和點 $y$ ,使得 $a_{xy} = 1$ 。而這個集合 $V$ 的權重就是所有在這個點集裡面的點的權重和,也就是

$$\sum_{i \in V} w_i$$

現在,請你找到權重和第 $K$ 小的獨立集。

建議看看範例輸入以獲得更詳細的資訊!

Input Format

以下變數若沒有特別說明,就跟題目敘述一樣。

輸入的第一行包含一個正整數 $T$ ,代表測試資料的個數。

對於每筆測試資料,第一行包含兩個整數 $N, K$ 。

接下來的 $N$ 行,第 $i$ 行有 $N$ 個整數,第 $j$ 個整數為 $a_{ij}$ 。

接下來的一行,包含 $N$ 個整數,第 $i$ 個整數為 $w_i$ 。

  • $1 \le T \le 7791$
  • $1 \le N \le 60$
  • $1 \le K \le 10^ 6$
  • $0 \le a_{ij} \le 1$
  • $0 \le w_i \le Fib_{60} = 1548008755920$

對於單一個輸入檔案:

  • 至多只會有 $330489$ 個數字
  • $K$ 的總和不超過 $10^ 6$

Output Format

對於每一筆測試資料,如果存在第 $K$ 小權重的話,請輸出該權重,否則請輸出 -1

Sample Input

8
2 1
0 1
1 0
1 3
2 2
0 1
1 0
1 3
2 3
0 1
1 0
1 3
2 4
0 1
1 0
1 3
3 3
0 1 0
1 0 1
0 1 0
1 3 2
3 4
0 1 0
1 0 1
0 1 0
1 3 2
3 5
0 1 0
1 0 1
0 1 0
1 3 2
3 6
0 1 0
1 0 1
0 1 0
1 3 2

Sample Output

0
1
3
-1
2
3
3
-1

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~50 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 8000 262144 262144 1
1 8000 262144 262144 1
2 8000 262144 262144 1
3 8000 262144 262144 1
4 8000 262144 262144 1
5 8000 262144 262144 1
6 8000 262144 262144 1
7 8000 262144 262144 1
8 8000 262144 262144 1
9 8000 262144 262144 1
10 8000 262144 262144 1
11 8000 262144 262144 1
12 8000 262144 262144 1
13 8000 262144 262144 1
14 8000 262144 262144 1
15 8000 262144 262144 1
16 8000 262144 262144 1
17 8000 262144 262144 1
18 8000 262144 262144 1
19 8000 262144 262144 1
20 8000 262144 262144 1
21 8000 262144 262144 1
22 8000 262144 262144 1
23 8000 262144 262144 1
24 8000 262144 262144 1
25 8000 262144 262144 1
26 8000 262144 262144 1
27 8000 262144 262144 1
28 8000 262144 262144 1
29 8000 262144 262144 1
30 8000 262144 262144 1
31 8000 262144 262144 1
32 8000 262144 262144 1
33 8000 262144 262144 1
34 8000 262144 262144 1
35 8000 262144 262144 1
36 8000 262144 262144 1
37 8000 262144 262144 1
38 8000 262144 262144 1
39 8000 262144 262144 1
40 8000 262144 262144 1
41 8000 262144 262144 1
42 8000 262144 262144 1
43 8000 262144 262144 1
44 8000 262144 262144 1
45 8000 262144 262144 1
46 8000 262144 262144 1
47 8000 262144 262144 1
48 8000 262144 262144 1
49 8000 262144 262144 1
50 8000 262144 262144 1