亚洲综合视频网,国产一区二区毛片,在线欧美不卡

對(duì)于蝸牛來說，狂奔雖不代表極速，但展現(xiàn)的卻是一種拼盡全力的姿態(tài)........

pku 1419

2009年8月9日

題目鏈接：PKU 1419 Graph Coloring

分類：DFS

題目分析與算法原型
         算法1：直接暴力搜索即可過，數(shù)據(jù)不強(qiáng)，實(shí)現(xiàn)默認(rèn)每個(gè)點(diǎn)為白色，然后從第一個(gè)點(diǎn)開始搜索，對(duì)于當(dāng)前的頂點(diǎn)，枚舉與他相鄰的點(diǎn)中是否有黑色，若沒有則將他染黑色，然后頂點(diǎn)編號(hào)加一，繼續(xù)搜索下一個(gè)，若與他相鄰的點(diǎn)中有已經(jīng)染黑的點(diǎn)，那么只能將當(dāng)前的點(diǎn)染成白色，然后繼續(xù)搜索，注意無論有沒有黑色的鄰點(diǎn)，對(duì)于當(dāng)前的點(diǎn)都要染白一次，搜索，因?yàn)閷?duì)于白色是沒有限制的....
        算法2：其實(shí)這是一道最大獨(dú)立集問題，對(duì)于該種問題可以通過將原圖求補(bǔ)，就可以變成求其補(bǔ)圖的最大團(tuán)問題，通過最大團(tuán)來求解
       （PS：算法1->47ms,算法2->0ms）

Code1:

1

#include<stdio.h>
2

#include<string.h>
3

#define max 105
4

bool flag[max];
5

int map[max][max],t,n,k,color[max],count,pos[max],fp,black,cnt;//color數(shù)組：0表示白，1表示黑
6

void dfs(int num)
7

{
8

int i;
9

if(num==n)
10

{
11

int j;
12

if(black>count)
13

{
14

fp=0;
15

count=black;
16

for(j=1;j<=n;j++)if(color[j]==1)pos[fp++]=j;
17

}
18

return ;
19

}
20

for(i=1;i<=n;i++)
21

if(i!=num&&map[num][i]==1&&color[i]==1)break;
22

if(i>n)
23

{
24

color[num]=1;
25

black++;
26

dfs(num+1);
27

color[num]=0;
28

black--;
29

}
30

dfs(num+1);
31

}
32

int main()
33

{
34

int i;
35

scanf("%d",&t);
36

while(t--)
37

{
38

memset(flag,false,sizeof(flag));
39

memset(map,0,sizeof(map));
40

memset(color,0,sizeof(color));
41

scanf("%d%d",&n,&k);
42

for(i=1;i<=k;i++)
43

{
44

int a,b;
45

scanf("%d%d",&a,&b);
46

map[a][b]=1;
47

map[b][a]=1;
48

}
49

count=0;
50

black=0;
51

dfs(1);
52

printf("%d\n",count);
53

for(i=0;i<fp;i++)
54

{
55

printf("%d",pos[i]);
56

if(i<fp-1)printf(" ");
57

else printf("\n");
58

}
59

}
60

return 1;
61

}
62

63

Code2:

1

#include<stdio.h>
2

#define len 105
3

int map[len][len],max,cnt[len],group[len],m,n,k;
4

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

{
6

int i,j;
7

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

{
9

if(cnt[i]+pos<=max) return false;//根據(jù)cnt[]數(shù)組的非遞增性可以直接返回false
10

if(map[num][i])
11

{
12

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

if(j==pos) //與當(dāng)前完全圖的所有點(diǎn)都有邊，可以加進(jìn)來
14

{
15

visit[pos]=i;
16

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

}
18

}
19

}
20

if(pos>max)
21

{
22

int kk;
23

for(kk=0;kk<pos;kk++)group[kk]=visit[kk];//更新最大完全圖的頂點(diǎn)集合
24

max=pos;
25

return true;//根據(jù)cnt[]數(shù)組的非遞增性可以直接返回true
26

}
27

return false;
28

}
29

void init()
30

{
31

int i,j;
32

for(i=1;i<=n;i++)
33

for(j=1;j<=n;j++)
34

{
35

if(i!=j)map[i][j]=1;
36

else map[i][j]=0;
37

}
38

}
39

int main()
40

{
41

int i,a,b,path[len];
42

scanf("%d",&m);
43

while(m--)
44

{
45

scanf("%d%d",&n,&k);
46

init();
47

for(i=1;i<=k;i++)
48

{
49

scanf("%d%d",&a,&b);
50

map[a][b]=0;
51

map[b][a]=0;
52

}
53

54

max=-1;
55

for(i=n;i>=1;i--)
56

{
57

path[0]=i;
58

dfs(i,path,1);
59

cnt[i]=max;
60

}
61

printf("%d\n",cnt[1]);//打印出最大完全圖的頂點(diǎn)數(shù)
62

for(i=0;i<cnt[1];i++)printf("%d ",group[i]);//打印出最大完全圖的頂點(diǎn)集合
63

printf("\n");
64

}
65

return 1;
66

}

posted on 2009-08-09 10:00 蝸牛也Coding 閱讀(334) 評(píng)論(0) 編輯收藏引用

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



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

<

2025年9月

>

日

一

二

三

四

五

六

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

導(dǎo)航

統(tǒng)計(jì)

隨筆 - 78
文章 - 0
評(píng)論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 94776
排名 - 261

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品