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
 4bool flag[max];
 5int map[max][max],t,n,k,color[max],count,pos[max],fp,black,cnt;//color数组：0表示白，1表示黑
 6void 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}
32int 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
 3int map[len][len],max,cnt[len],group[len],m,n,k;
 4bool 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}
29void 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}
39int 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 阅读(352) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜