• <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)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    




            






            

				
				

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

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



四虎国产精品成人免费久久|
狠狠久久综合|
久久天天躁狠狠躁夜夜avapp|
久久久久亚洲av成人网人人软件|
亚洲精品无码久久千人斩|
www久久久天天com|
久久综合鬼色88久久精品综合自在自线噜噜
|
久久亚洲国产精品123区|
久久亚洲sm情趣捆绑调教|
久久久精品人妻一区二区三区四|
91久久精品无码一区二区毛片|
亚洲欧美一区二区三区久久|
国内精品伊人久久久久|
色妞色综合久久夜夜|
久久91精品国产91久久小草|
日韩精品久久久久久久电影|
国产成人综合久久综合|
久久久噜噜噜久久中文字幕色伊伊
|
婷婷久久综合九色综合98|
欧洲性大片xxxxx久久久|
2020久久精品国产免费|
色青青草原桃花久久综合|
久久久久免费精品国产|
亚洲国产另类久久久精品小说|
久久艹国产|
色综合久久精品中文字幕首页
|
伊人久久一区二区三区无码|
香蕉久久一区二区不卡无毒影院|
嫩草伊人久久精品少妇AV|
中文国产成人精品久久亚洲精品AⅤ无码精品
|
国产农村妇女毛片精品久久|
91视频国产91久久久|
久久这里只有精品18|
亚洲女久久久噜噜噜熟女|
一日本道伊人久久综合影|
久久久久国产一区二区三区|
国产精品VIDEOSSEX久久发布|
国产成人久久精品麻豆一区|
伊人丁香狠狠色综合久久|
久久777国产线看观看精品|
国产亚洲婷婷香蕉久久精品|