亚洲综合日韩,国产主播一区二区三区,欧美亚一区二区

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

#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 閱讀(546) 評論(0) 編輯收藏引用

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



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

zju 1492

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜