• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年8月>
            
	
            日一二三四五六
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



欧美久久一级内射wwwwww.|
国产AV影片久久久久久|
国内精品综合久久久40p|
久久强奷乱码老熟女网站|
久久亚洲AV无码精品色午夜|
色婷婷久久综合中文久久蜜桃av|
精品国产青草久久久久福利|
精品久久亚洲中文无码|
色综合久久精品中文字幕首页
|
亚洲国产精品无码久久久蜜芽
|
久久性生大片免费观看性|
久久天天躁狠狠躁夜夜不卡|
精品久久久久久久国产潘金莲
|
伊人情人综合成人久久网小说|
九九久久精品无码专区|
中文字幕久久精品|
99精品久久精品|
午夜欧美精品久久久久久久|
天天久久狠狠色综合|
久久久久高潮综合影院|
久久国产三级无码一区二区|
色88久久久久高潮综合影院|
久久精品国产99久久丝袜|
69SEX久久精品国产麻豆|
日本精品久久久久影院日本|
国产成人精品久久一区二区三区|
色天使久久综合网天天|
久久国产香蕉视频|
东京热TOKYO综合久久精品|
亚洲中文字幕无码久久综合网|
亚洲国产小视频精品久久久三级
|
欧美综合天天夜夜久久|
国产成人久久精品一区二区三区|
久久99国产精品久久99果冻传媒|
精品综合久久久久久88小说|
青青青国产精品国产精品久久久久|
国产精品乱码久久久久久软件|
国产 亚洲 欧美 另类 久久|
99久久婷婷国产综合亚洲|
一本色道久久综合亚洲精品|
欧美与黑人午夜性猛交久久久|