• <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)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



品成人欧美大片久久国产欧美|
伊人久久大香线蕉av不变影院
|
精品久久久无码人妻中文字幕|
国产2021久久精品|
99久久精品无码一区二区毛片|
69久久精品无码一区二区|
久久精品亚洲中文字幕无码麻豆|
久久综合给合久久国产免费
|
精品国产91久久久久久久a|
久久婷婷久久一区二区三区
|
国产精品免费看久久久香蕉|
国产成人久久精品麻豆一区|
久久精品一区二区影院|
久久亚洲av无码精品浪潮|
久久亚洲欧洲国产综合|
99久久国产综合精品女同图片|
亚洲va久久久噜噜噜久久狠狠|
蜜臀久久99精品久久久久久小说
|
久久国产高清一区二区三区|
久久久久久免费视频|
久久狠狠高潮亚洲精品|
国产激情久久久久影院老熟女免费|
久久无码一区二区三区少妇
|
精品久久久久国产免费|
久久人妻无码中文字幕|
久久精品欧美日韩精品|
久久伊人五月天论坛|
久久久亚洲AV波多野结衣|
国产精品久久久久久一区二区三区|
国产精品永久久久久久久久久|
伊人色综合久久天天人守人婷|
久久久精品国产sm调教网站
|
久久精品国产黑森林|
久久婷婷五月综合国产尤物app
|
久久久国产精品网站|
一本色道久久88综合日韩精品|
97久久超碰国产精品旧版|
亚洲?V乱码久久精品蜜桃|
青青青国产成人久久111网站|
7777精品久久久大香线蕉|
久久精品无码免费不卡|