Re: [ＡCM] 193 - Graph Coloring

[LPH66 (-858993460)]

※ 引述《jason3e7 (小綠)》之銘言：
:         ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
:              ( 未必需要依照此格式，文章條理清楚即可 )
: 題號：193
: 遇到的問題：WA
: 有問題的code：http://nopaste.csie.org/1a846 (請善用置底文的標色功能)
: 補充說明：
: 網路上我有找到解法是全部搜尋一次
: 不過我想從最少邊的連接點填黑色開始
: 不知道這樣的概念錯在哪
: 請幫忙舉個反例 謝謝
:
反例來了:

1
9 17
1 2
1 3
2 4
2 5
2 6
3 4
3 5
3 6
4 7
4 8
4 9
5 7
5 8
5 9
6 7
6 8
6 9

(補圖: http://w.csie.org/~b94102/math/Math36a.png )

一組答案:

5
2 3 7 8 9

你的答案:

4
1 7 8 9

--
**** 說:
不要期望一個精神力差不多已經見底的人阿Orz

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.68
推 jason3e7:感謝 ^^
→ loveme00835:可以試試 : degree 最大的塗白色
→ suhorng:這題記得只能爆搜吧...
degree 最大塗白色也不對

以下是個(頗大的)反例:

//不想研究測資的可點圖
//http://w.csie.org/~b94102/math/Math36b.png
//正解是 9                       而 7~11 這五個點各是 degree 8 是圖中最多
//       1 2 7 8 9 10 11 16 17

1
17 56
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 7
3 8
3 9
3 10
3 11
4 7
4 8
4 9
4 10
4 11
5 7
5 8
5 9
5 10
5 11
6 7
6 8
6 9
6 10
6 11
7 12
7 13
7 14
7 15
8 12
8 13
8 14
8 15
9 12
9 13
9 14
9 15
10 12
10 13
10 14
10 15
11 12
11 13
11 14
11 15
12 16
12 17
13 16
13 17
14 16
14 17
15 16
15 17

※ 編輯: LPH66           來自: 140.112.28.92        (07/23 01:43)
推 loveme00835:原來如此=  =
→ jason3e7:我乖乖用暴力搜尋做吧