精品国产青草久久久久福利,久久免费视频6,亚州日韩精品专区久久久

zju 1492

2009年8月11日

題目鏈接：ZJU 1492 Maximum Clique

分類：典型的NP問題之最大團(tuán)

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

Code:

1

#include<stdio.h>
2

#include<string.h>
3

#define len 55
4

int map[len][len],n,max,cnt[len];
5

bool dfs(int num,int visit[len],int pos)
6

{
7

int i,j;
8

for(i=num+1;i<n;i++)
9

{
10

if(cnt[i]+pos<=max) return false;
11

if(map[num][i])
12

{
13

for(j=0;j<pos;j++)if(map[i][visit[j]]==0)break ;
14

if(j==pos)
15

{
16

visit[pos]=i;
17

if(dfs(i,visit,pos+1))return true;
18

}
19

}
20

}
21

if(pos>max)
22

{
23

max=pos;
24

return true;
25

}
26

return false;
27

}
28

int main()
29

{
30

while(scanf("%d",&n)!=EOF&&n)
31

{
32

int i,j,path[len];
33

for(i=0;i<n;i++)
34

for(j=0;j<n;j++)scanf("%d",&map[i][j]);
35

max=-1;
36

for(i=n-1;i>=0;i--)
37

{
38

path[0]=i;
39

dfs(i,path,1);
40

cnt[i]=max;
41

}
42

printf("%d\n",cnt[0]);
43

}
44

return 1;
45

}

posted on 2009-08-11 18:01 蝸牛也Coding 閱讀(536) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

zju 1492

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜