亚洲国产欧美一区二区三区久久,在线观看日产精品,国产一区二区三区免费观看

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

pku 1419

2009年8月9日

題目鏈接：PKU 1419 Graph Coloring

分類：DFS

題目分析與算法原型
         算法1：直接暴力搜索即可過，數據不強，實現默認每個點為白色，然后從第一個點開始搜索，對于當前的頂點，枚舉與他相鄰的點中是否有黑色，若沒有則將他染黑色，然后頂點編號加一，繼續搜索下一個，若與他相鄰的點中有已經染黑的點，那么只能將當前的點染成白色，然后繼續搜索，注意無論有沒有黑色的鄰點，對于當前的點都要染白一次，搜索，因為對于白色是沒有限制的....
        算法2：其實這是一道最大獨立集問題，對于該種問題可以通過將原圖求補，就可以變成求其補圖的最大團問題，通過最大團來求解
       （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數組：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;//根據cnt[]數組的非遞增性可以直接返回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) //與當前完全圖的所有點都有邊，可以加進來
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];//更新最大完全圖的頂點集合
24

max=pos;
25

return true;//根據cnt[]數組的非遞增性可以直接返回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]);//打印出最大完全圖的頂點數
62

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

printf("\n");
64

}
65

return 1;
66

}

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

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



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