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


	


            
	    
    




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2009年7月>
            
	
            日一二三四五六
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



久久99久久99精品免视看动漫|
人妻精品久久无码区|
久久免费视频一区|
亚洲伊人久久精品影院|
国内精品久久久久久中文字幕|
精品熟女少妇AV免费久久|
韩国无遮挡三级久久|
国产精品成人久久久|
成人亚洲欧美久久久久|
久久Av无码精品人妻系列
|
国产精品久久久香蕉|
亚洲国产精品久久久久网站|
无码人妻久久久一区二区三区|
久久久久国产一级毛片高清板|
99久久超碰中文字幕伊人|
久久精品人妻中文系列|
亚洲国产成人久久一区WWW|
Xx性欧美肥妇精品久久久久久|
国产精品久久久久AV福利动漫|
欧美黑人激情性久久|
亚洲美日韩Av中文字幕无码久久久妻妇|
色综合久久中文色婷婷|
久久se精品一区精品二区|
老色鬼久久亚洲AV综合|
无码精品久久久久久人妻中字|
一级做a爰片久久毛片看看|
亚洲人AV永久一区二区三区久久|
久久se这里只有精品|
久久99精品九九九久久婷婷|
国产高潮国产高潮久久久91
|
热久久这里只有精品|
亚洲精品高清久久|
久久国产视屏|
久久亚洲精品国产亚洲老地址|
亚洲国产成人久久精品99|
亚洲国产日韩欧美久久|
亚洲综合伊人久久大杳蕉|
久久w5ww成w人免费|
大美女久久久久久j久久|
青青热久久国产久精品
|
久久精品国产久精国产思思|