#15137: 題目敘述


2qbingxuan (程式初學者)

School : 臺北市立建國高級中學
ID : 58274
IP address : [114.32.125.176]
Last Login :
2022-03-20 12:00:11
b839. 104北二3.朋友 -- 104北二區桃竹苗基資訊學科能力複賽 | From: [223.140.226.160] | Post Date : 2018-09-15 20:12

...每個團體中的任意兩個人都是朋友,而兩個不同團體中的人則都不是朋友。...

 

請問兩個團體之間的人都不是朋友嗎?那本題是要求最大子完全圖(不確定是否稱呼正確)還是最大連通塊?

並想請教 如果是前者該怎麼做...想到的只有 O(2^n) 作法..

 
#19123: Re:題目敘述


easylin0126@gmail.com (林榮翼)

School : 臺北市立成功高級中學
ID : 89424
IP address : [42.72.26.114]
Last Login :
2021-11-02 16:27:48
b839. 104北二3.朋友 -- 104北二區桃竹苗基資訊學科能力複賽 | From: [106.105.1.190] | Post Date : 2019-09-01 17:27

...每個團體中的任意兩個人都是朋友,而兩個不同團體中的人則都不是朋友。...

 

請問兩個團體之間的人都不是朋友嗎?那本題是要求最大子完全圖(不確定是否稱呼正確)還是最大連通塊?

並想請教 如果是前者該怎麼做...想到的只有 O(2^n) 作法..

我是用並查集過的,方法是枚舉所有兩兩的組合,如果符合"LCS長度不小於min(m,n)/2.0",就把他們連在一起,在完全沒有任何優化的情況下AC (16ms, 108KB),不知道有沒有其他解法> <


 
ZeroJudge Forum