国产精品久久久久aaaa,韩国成人精品a∨在线观看,国产精品theporn88

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

zju 1492

2009年8月11日

題目鏈接：ZJU 1492 Maximum Clique

分類：典型的NP問題之最大團

題目分析與算法原型
這是一個最大團問題，老實說，這道題已經TLE了好多次，之后由于細節上的一個錯誤又WA了幾次（TLE就算了，還WA了，真有必要BS下自己），先前簡直就是直接暴力DFS，然后才發現這題不愧是NP問題，10秒的限時都被我超了（看來這種問題還是不能有僥幸心理，orz......）
當然這題也是可以在我原先的想法上減枝的，我原先的想法是從0開始一直到n-1枚舉每個點進行一次dfs,因為問題求的是最大的完全子圖的頂點數，所以，我每加進來一個點，枚舉和其相鄰的點x，判斷下x是否和已經加近來的點（用一個數組記錄當前已經找到的最大的完全圖的各個頂點編號）都有邊，當且僅當和里面所有的點都有邊時候才把x加入.........思路是比較清晰，但是這復雜度簡直不可想象，其實有個比較好的方法（小Q同學的提醒），從n-1到0枚舉每個點，保存一個數組cnt[],其中cnt[i]記錄的是從頂點i一直到n-1這些點中找到的完全圖的最大頂點數（那么原問題就是求cnt[0]），到這里那么我們可以發現cnt[i-1]=cnt[i]或者cnt[i]+1，這一步的發現很重要，因為是一個很有力的減枝，每次從傳入的頂點編號num的下個num+1到n-1找與num相鄰的點，設當前枚舉的是i,若當前找到的完全圖的頂點數+cnt[i]<=max（max為現在找到的所有完全圖的最大頂點數）那么直接返回false，因為cnt[]數組是非遞增的，所有以后的都可以不用考慮了，還有根據cnt數組的這一個非遞增的特性，一旦某次更新了max，也就可以直接返回true了..........

Code:

1